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.