In this module, in
the next slide, what we're going to do is
look at a library that implements a queue:
last in, first out. It's going to be written in
the C programming language in the way that most C programmers
would normally write it. Now, why are we doing
it this way instead of just telling you the problems? Because it's always
fun to pick apart someone's code and
the instructor wrote this. So, don't worry about
picking on someone else. In this library which is
called from programs, there are two files. Queue.h that contains the data structures
and the constants, and it defines the type queue. Then, queue.c is
simply the set of library functions that would be compiled and put into a library, and then linked into the program
at the appropriate time. On the next slide, in queue.h, we see the actual
queue structure. We have a pointer to an array of queue elements and the
elements are all integers. We also have the index in that array of the first
element in the queue, which is the head and the number of elements in
the queue, which is the count. Note that the queue
may wrap around. So if it goes to the end, the one after the end is at
the beginning of the array. But the beginning of the queue is the element at the index number
contained in head. Then, size is the maximum number of elements that can
go into the queue. As I said, all of this is
called the Queue Structure. In that file also
on the next slide, it shows the prototypes
for the functions. We have three functions here. The first is qmanage, which manages the creating and
deleting queues basically. It takes as an argument
the address of a pointer to the queue
to double pointer. So you'll pass in a
pointer and then, that will come back. When the function returns, that pointer will
have the address of the queue structure. Then, it takes
two other integers, one for an indication
of whether or not you're creating or
deleting a queue, and then another if you're
creating it for the size. Then, adding something
to the end of the queue is the put on queue, and you just pass it in
as an integer and you give it the pointer to
the queue structure. Then, taking an element
from the head of the queue. Again, you pass in a pointer
to the queue structure, but this time you pass in the address where you want
the integer to be stored. Because if you remember from C, everything is passed by value. Nothing is passed by reference, so you do a pointer to
make it pass by reference. Here's the puzzle. Let's say the programmer wants to change the number of
elements in the queue. So, the programmer's going
to create the queue. Then, say, "Well, we've
already got 99 elements in it, instead of zero elements in it." I'm not sure why they
would want to do this. But let's say either they want to do it or it
happens accidentally. There's the code for it. You create a pointer to the queue and you
pass in its address. One means create and 100 means the queue size
is going to be 100. We then set the count
to 99. What happens? Even though nothing's
been inserted. I'll give you a minute
to think about that. All right. What's going to
happen is absolutely nothing. As far as the library's
concerned that queue now is 99 elements. What are those elements? Well, head is going to be zero. So, it will be whatever
happens to be contained in the first 99 elements
of that queue array, and that's almost certainly junk. So this is an example of
a problem that can arise in a fragile library by changing something of the
eternal data structure, which the library
routines rely upon, the caller can mess
things up pretty badly. Okay. So now, let's go to
the Queue Management Routine. The next couple of
slides have this. Basically, you can
see what it does. It takes a couple of parameters. The first being,
as you saw early, the address of the queue pointer. The second being a flag. If the flag is one, the queue gets created
and if it's zero, it gets deleted,
that's the intent. Then the size is the maximum number of
elements in the queue. So first of all, let's
starts off by deciding does it create or delete a
queue by looking at flag. If flag is non-zero, it's going to create a new queue. So, it malloc space, allocate space for it. Then, sets the head
and the count to zero, because there's nothing in the queue and so we might as well start at the beginning
of the queue array. It then allocates space for
the actual queue itself. It's going to be storing a number of integers and the number
is in the size. So that's what
the second malloc does. Then, you've got size, the size of the queue is equal to the parameter
that's passed through. So that's the creation
of the queue. If flag is zero, then you go to the else. The first thing you do is delete the elements of the queue. That's what the first one
does in a corresponds to the second malloc
in the if above. Then, you actually free the
queue structure itself, which corresponds to the first
malloc in the line above. So now, here's an interesting
exercise for you. How many things can you find
here that can go wrong? Let's wait a minute and
then we'll go ahead. All right. First,
let's look at what can go wrong internal
to the queue. First of all,
the mallocs may fail. If they fail, they return
null, the null pointer. If the first one fails, then the next line which is assigned a value
to head and count, dereferences a null pointer which will cause
the program to crash. So, that's not good. The second thing
that can go wrong, is the space allocated
to the queue. Let's say we're working
on a 32-bit machine, and size of int is four bytes. If you try to allocate a queue
of size two to the 31st, that multiplication in
the second malloc's argument is going to overflow. When it overflows, you're
going to get a two, because two to the 31st
times two squared, which is the four,
is two to the 33rd. That causes an overflow, and I'm sorry you don't
get two, you get zero. So, what happens when
malloc is called with zero? Well, one of two things. It either return zero
or returns a pointer to a space with room
for zero elements. In the first case, in either case actually, you won't detect this error. But the first time you
tried to put anything into the queue, you'll
find the error. If you're lucky,
your program will crash at that point in
the library routine. If you're not lucky, it's going
to go ahead and continue. Heaven only knows what's
going to happen after that. The third thing that's internal
here is you do the free. Then, if the
queue pointer is null and you do the free,
that will not work. If trying to free a null pointer, either causes a crash
or simply does nothing. Okay. So now, let's look
at what can happen, go wrong when you
call this routine. First one is that the address of queue pointer
could be empty, that could be null
or it could point to something else like
characters or an integer, or whatever because C doesn't do type checking
accurately or well. So, when you try to
assign malloc to it, the malloc value to
it the first one, it could quite easily crash. So, one of the problems here
is that first argument, there's really no way to
check it for validity. You can check to be sure
that it's not null, but that's about all you can do. The second one is, let's say I delete a queue. Queue pointer nowhere
is set to null. So if I call qmanage
again to delete it, when it goes into the else, it'll basically do a double free. It'll free something
that's already been freed. That is a very good way to
cause the program to crash, or an attacker might be
able to exploit that. Double free errors
are quite well known as a potential security
vulnerability. The third is a
little bit trickier. Look at flag. What happens
if I call it with five? Well, it's non-zero. So the if statement with
flag will be executed. That seems okay but
here's the problem. In flag and in size, it's very easy to confuse the order of
those two parameters. Problem is if I flipped them, so sizes one and flag is 100. There's no indication. I'll get a queue of size one. So that's another problem. How do you call this? It also illustrates
an important point about robust programming and
secure programming. You want to make sure that it's very hard for the user to cause problems or for the caller in this case to cause problems. So, if you look at next slide, it gives you some examples of what can go wrong. All right. Now, here's adding
an element to the queue. Again, we pass in a pointer to the queue and the number
we want to add. We just do the usual, go to the end of the queue. That's what the qptr arrow head plus qptr arrow count does. If it's beyond
the end of the queue, we reduce it mod size
of the queue. Then, we put n there, and then we add one to count. Again, let's take a look at how many ways things
can go wrong. Clearly the first
argument's validity can't be checked for the reasons
stated earlier. But the second one is, what happens if head
is negative four? Because since the qptr structure was visible to the caller, the caller may have
somehow messed it up. There's no sanity
checking on any of the elements of qptr
before you use them. The last one is, supposed size is 100
and count is 100, and they call this routine. So we have an array for
the queue with 100 spaces, but all 100 are filled.
What happens here? Well, what happens is, the
head gets overwritten with n, n count goes up to 101. So there's no indication of any error or any
overflow, whatsoever. The next slide states these. The last routine is take_off_queue and routine
of a qptr is before. But now since you're storing
a value from the queue, you pass the address of the integer variable where you want that value to be placed. Again, this is straightforward. Get the element from
the head of the queue, store in where n points to, and advance the head. So now, you basically remove the first element
from the head. You've got one less than
the count, so subtract that. If this was at the end of that array representing
the queue, you may have gone beyond the n when you added one to head. So you reduce it mod size. Again, very straightforward. Now, what can go wrong here? Well, I will not repeat
all the stuff about the qptr. But let's instead take a look at the int star n in
the parameter list. How do you know that
points to an integer? How do you know it's not null? In either case, if it's
not an integer pointer, the first line may
mess up very badly. It may cause a crash,
if you're lucky. If you're not lucky,
it's going to do something that's
unpredictable. There's no check here
also for underflow. Suppose the queue is empty. Well, in that case, it'll pull whatever garbage, or whatever happens to be in the memory location
that had indexes. So I have absolutely no
indication of error. Again as I said before
in the previous one, how would you know head, size, and count were changed
external to the library? Okay. So that's
the non-robust version. Let's now go to
the robust version.