[Week 5]
[David J. Malan - Harvard University]
[This is CS50. - CS50.TV]
>> This is CS50, Week 5.
Today and this week, we introduce a little bit of the world of forensics
in the context of the Problem Set 4.
Today will be an abbreviated lecture because there's a special event in here afterwards.
So we'll take a peek and tease both students and parents alike today
with some of the things that are on the horizon.
>> Among them, as of Monday, you will have a few more classmates.
edX, Harvard and MIT's new online initiative for OpenCourseWare and more,
is launching on Harvard's campus on Monday, which means come Monday
you will have, as of last count, 86,000 additional classmates
who will be following along with CS50's lectures and sections
and walkthroughs and problem sets.
And as part of this, you will become members of the inaugural class of CS50 and now CS50x.
As part of this now, realize that there will be some upsides as well.
To get ready for this, for the massive number of students,
suffice it to say that even though we have 108 TFs and CAs,
it's not quite the best student-teacher ratio once we hit 80,000 of the students.
We're not going to be grading so many problem sets manually,
so introduced this week in the problem set will be CS50 Check,
which is going to be a command-line utility within the appliance
that you'll get once you update it later this weekend.
You'll be able to run a command, check50, on your own pset,
and you'll get instant feedback as to whether your program is correct or incorrect
according to various design specifications that we have provided.
More on that in the problem set specification.
The CS50x classmates will be using this as well.
>> Problem Set 4 is all about forensics,
and this pset was really inspired by some real-life stuff
whereby when I was in graduate school I interned for a while
with Middlesex County's District Attorney's office doing forensic work
with their lead forensic investigator.
What this amounted to, as I think I mentioned a few weeks past,
is the Mass State Police or others would come in,
they would drop off things like hard drives and CDs and floppy disks and the like,
and then the goal of the forensics office was to ascertain
whether there was or was not evidence of some sort.
This was the Special Investigations Unit, so it was white-collar crime.
It was more troubling sort of crimes, anything involving some kind of digital media.
It turns out that not that many people write an email saying, "I did it."
So quite often, these forensic searches did not turn up all that much fruit,
but sometimes people would write such emails.
So sometimes, the efforts were rewarded.
>> But to lead up to this forensic pset, we'll be introducing in pset4 a bit of graphics.
You probably take these things for granted--JPEGs, GIFs, and the like--these days.
But if you really think about it, an image, much like Rob's face,
could be modeled as a sequence of dots or pixels.
In the case of Rob's face, there's all sorts of colors,
and we started to see the individual dots, otherwise known as pixels,
once we started to zoom in.
But if we simplify the world a bit and just say that this here is Rob in black and white,
to represent black and white, we can just use binary.
And if we're going to use binary, 1 or 0, we can express this same image
of Rob's smiling face with this pattern of bits.
11000011 represents white, white, black, black, black, black, white, white.
And so it's not a huge leap then to start talking about colorful photographs,
things that you'd see on Facebook or take with a digital camera.
But certainly when it comes to colors, you need more bits.
And quite common in the world of photographs is to use not 1-bit color,
as this suggests, but 24-bit color, where you actually get millions of colors.
So as in the case when we zoomed in on Rob's eye,
that was any number of millions of different colorful possibilities.
So we'll introduce this in Problem Set 4 as well as in the walkthrough,
which will be today at 3:30 instead of the usual 2:30 because of Friday's lecture here.
But video will be online as usual tomorrow.
>> We'll also introduce you to another file format.
This is deliberately meant to look intimidating at first,
but this is just some documentation for a C struct.
It turns out that Microsoft years ago helped popularize this format
called the bitmap file format, bmp, and this was a super simple, colorful graphical file format
that was used for quite some time and sometimes still for wallpapers on desktops.
If you think back to Windows XP and the rolling hills and the blue sky,
that was typically a bmp or bitmap image.
Bitmaps are fun for us because they have a bit more complexity.
It's not quite as simple as this grid of 0s and 1s.
Instead, you have things like a header at the start of a file.
So in other words, inside of a .bmp file is a whole bunch of 0s and 1s,
but there's some additional 0s and 1s in there.
And it turns out that what we've probably taken for granted for years--
file formats like .doc or .xls or .mp3, .mp4, whatever the file formats
that you're familiar with--what does it even mean to be a file format,
because at the end of the day all of these files we use have just 0s and 1s.
And maybe those 0s and 1s represent ABC through ASCII or the like,
but at the end of the day, it's still just 0s and 1s.
So humans just occasionally decide to invent a new file format
where they standardize what patterns of bits will actually mean.
And in this case here, the folks who designed the bitmap file format
said that at the very first byte in a bitmap file, as denoted by offset 0 there,
there is going to be some cryptically named variable called bfType,
which just stands for bitmap file type, what type of bitmap file is this.
You can infer perhaps from the second row that offset 2, byte number 2,
has a pattern of 0s and 1s that represents what? The size of something.
And it goes on from there.
So in Problem Set 4, you'll be walked through some of these things.
We won't end up caring about all of them.
But notice it starts to get interesting around byte 54: rgbtBlue, Green, and Red.
If you've ever heard the acronym RGB--red, green, blue--this is a reference to that
because it turns out you can paint all the colors of the rainbow
with some combination of red and blue and green.
And in fact, parents in the room might recall some of the earliest projectors.
These days, you just see one bright light coming out of a lens,
but back in the day you had the red lens, the blue lens, and the green lens,
and together they aimed at a screen and formed a colorful picture.
And quite often, middle schools and high schools would have those lenses
ever so slightly askew, so you were sort of seeing double or triple images.
But that was the idea. You had red and green and blue light painting a picture.
And that same principle is used in computers.
>> So among the challenges then for you in Problem Set 4 are going to be a few things.
One is to actually resize an image, to take in a pattern of 0s and 1s,
figure out which chunks of 0s and 1s represent what in a structure like this,
and then figure out how to replicate the pixels--the reds, the blues, the greens--
inside so that when a picture looks like this initially,
it might look like this instead after that.
Among the other challenges too is going to be that you'll be handed a forensic image
of an actual file from a digital camera.
And on that camera, once upon a time, were a whole bunch of photos.
The problem is we accidentally erased or had the image corrupted somehow.
Bad things happen with digital cameras.
And so we quickly copied all of the 0s and 1s off of that card for you,
saved them all in one big file, and then we'll hand them to you in Problem Set 4
so that you can write a program in C with which to recover all of those JPEGs, ideally.
And it turns out that JPEGs, even though they're somewhat of a complex file format--
they're much more complex than this smiling face here--
it turns out that every JPEG starts with the same patterns of 0s and 1s.
So using, ultimately, a while loop or a for loop or similar,
you can iterate over all the 0s and 1s in this forensic image,
and every time you see the special pattern that's defined in the problem set specification,
you can assume here is, with very high probability, the start of a JPEG.
And as soon as you find the same pattern some number of bytes
or kilobytes or megabytes later, you can assume here is a second JPEG,
the photo I took after the first one.
Let me stop reading that first file, start writing this new one,
and the output of your program for pset4 is going to be as many as 50 JPEGs.
And if it's not 50 JPEGs, you have a bit of a loop.
If you have an infinite number of JPEGs, you have an infinite loop.
So that too will be quite a common case.
So that's what's on the horizon.
>> Quiz 0 behind us, realize per my email that invariably there are folks who are both happy,
sort of neutral, and sad around quiz 0 time.
And please do reach out to me, the head TF Zamyla, your own TF,
or one of the CAs that you know if you would like to discuss how things went.
>> So to impress the parents here in the room, what is the CS50 library?
[laughter] Good job.
What's the CS50 library? Yeah. >>[student] It's a pre-written set of code [inaudible]
Okay, good.
It's a pre-written set of code that we the staff wrote, we provide to you,
that provides some common functionality,
stuff like get me a string, get me an int--all of the functions that are listed here.
>> Starting now, we start to really take these training wheels off.
We're going to start to take away a string from you,
which recall was just a synonym for what actual data type? >>[multiple students] Char*.
Char*. For parents, that was probably [makes whooshing sound]. That's good.
Char* we'll start to see on the screen all the more as we remove string from our vocabulary,
at least when it comes to actually writing code.
Similarly, we'll stop using some of these functions as much
because our programs are going to get more sophisticated.
Rather than just write programs that sit there with a prompt blinking,
waiting for the user to type something in, you'll get your inputs from elsewhere.
For instance, you'll get them from a series of bits on the local hard drive.
You'll instead get them in the future from a network connection,
some website somewhere.
>> So let's peel back this layer for the first time and pull up the CS50 Appliance
and this file called cs50.h, which you've been #including for weeks,
but let's actually see what's inside of this.
The top of the file in blue is just a whole bunch of comments:
warranty information and licensing.
This is sort of a common paradigm in software
because a lot of software these days is what's called open source,
which means that someone has written the code and made it freely available
not just to run and to use but to actually read and alter and integrate into your own work.
So that's what you've been using, open source software, albeit in a very small form.
If I scroll down past the comments, though, we'll start to see some more familiar things.
Notice at the top here that the cs50.h file includes a whole bunch of header files.
Most of these, we haven't seen before, but one is familiar.
Which of these have we seen, albeit briefly, thus far? >>[student] Standard library.
Yeah, standard library. stdlib.h has malloc.
Once we started talking about dynamic memory allocation,
which we'll come back to next week as well, we started including that file.
It turns out that bool and true and false don't actually exist in C per se
unless you include this file here.
We have for weeks been including stdbool.h
so that you can use the notion of a bool, true or false.
Without this, you would have to sort of fake it and use an int
and just arbitrarily assume that 0 is false and 1 is true.
If we scroll down further, here is our definition of a string.
It turns out, as we've said before, that where this star is doesn't really matter.
You can even have space all around.
We this semester have been promoting it as this to make clear
that the star has to do with the type,
but realize just as common, if not a little more common,
is to put it there, but functionally it's the same thing.
But now if we read down further, let's take a look at GetInt
because we used that perhaps first before anything else this semester.
Here is GetInt. This is what? >>[student] A prototype. >>This is just a prototype.
Often, we have put prototypes at the tops of our .c files,
but you can also put prototypes in header files, .h files, like this one here
so that when you write some functions that you want other people to be able to use,
which is exactly the case with the CS50 library,
you not only implement your functions in something like cs50.c,
you also put the prototypes not at the top of that file but at the top of a header file.
Then that header file is what friends and colleagues include
with #include in their own code.
So all this time, you've been including all of these prototypes,
effectively at the top of your file but by way of this #include mechanism,
which essentially copies and pastes this file into your own.
Here is some fairly detailed documentation.
We've pretty much taken for granted that GetInt gets an int,
but it turns out there are some corner cases.
What if the user types in a number that's way too big, a quintillion,
that just can't fit inside of an int? What is the expected behavior?
Ideally, it's predictable.
So in this case, if you actually read the fine print,
you'll actually see that if the line can't be read, this returns INT_MAX.
We've never talked about this, but based on its capitalization, what is it probably?
[student] A constant. >>It's a constant.
It's some special constant that's probably declared in one of those header files
that's up higher in the file, and INT_MAX is probably something like roughly 2 billion,
the idea being that because we need to somehow signify that something went wrong,
we, yes, have 4 billion numbers at our disposal: -2 billion on up to 2 billion, give or take.
Well, what is common in programming is you steal just one of those numbers,
maybe 0, maybe 2 billion, maybe -2 billion,
so you spend one of your possible values so that you can commit to the world
that if something goes wrong, I will return this super big value.
But you don't want the user typing something cryptic like 234..., a really big number.
You generalize it instead as a constant.
So really, if you were being anal the past few weeks, any time you called GetInt,
you should have been checking with an if condition did the user type in INT_MAX,
or, more specifically, did GetInt return INT_MAX, because if it did,
that actually means they didn't type it. Something went wrong in this case.
So this is what's generally known as a sentinel value, which just means special.
>> Let's now turn into the .c file.
The C file has existed in the appliance for some time.
And in fact, the appliance has it pre-compiled for you into that thing we called object code,
but it just doesn't matter to you where it is because the system knows
in this case where it is: the appliance.
Let's scroll down now to GetInt and see how GetInt has been working all this time.
Here we have similar comments from before.
Let me zoom in on just the code portion.
And what we have for GetInt is the following.
It takes no input.
It returns an int, while (true), so we have a deliberate infinite loop,
but presumably we'll break out of this somehow or return from within this.
>> Let's see how this works.
We seem to be using GetString in this first line inside the loop, 166.
This is now good practice because under what circumstances could GetString return
the special keyword NULL? >>[student] If something goes wrong.
If something goes wrong. And what could go wrong when you call something like GetString?
Yeah. >>[student] Malloc fails to give it the ints.
Yeah. Maybe malloc fails.
Somewhere underneath the hood, GetString is calling malloc, which allocates memory,
which lets the computer store all of the characters
that the user types into the keyboard.
And suppose the user had a whole lot of free time and typed more, for instance,
than 2 billion characters in, more characters than the computer even has RAM.
GetString has to be able to signify that to you.
Even if this is a super, super uncommon corner case,
it has to somehow be able to handle this,
and so GetString, if we went back and read its documentation, does in fact return NULL.
So now if GetString fails by returning NULL, GetInt is going to fail by returning INT_MAX
just as a sentinel. These are just human conventions.
The only way you would know this is the case is by reading the documentation.
>> Let's scroll down to where the int is actually gotten.
If I scroll down a bit further, in line 170, we have a comment above these lines.
We declare in 172 an int, n, and a char, c, and then this new function,
which some of you have stumbled across before, sscanf.
This stands for string scanf.
In other words, give me a string and I will scan it for pieces of information of interest.
What does that mean?
Suppose that I type in, literally, 123 at the keyboard and then hit Enter.
What is the data type of 123 when returned by GetString? >>[student] String.
It's obviously a string, right? I got a string.
So 123 is really, quote-unquote, 123 with the \0 at the end of it.
That is not an int. That's not a number. It looks like a number but it's not actually.
So what does GetInt have to do?
It has to scan that string left to right--123\0--and somehow convert to an actual integer.
You could figure out how to do this.
If you think back to pset2, you presumably got a little comfortable with Caesar
or Vigenere, so you can iterate over a string, you can convert chars to ints.
But heck, it's a whole lot of work.
Why not call a function like sscanf that does that for you?
So sscanf expects an argument--in this case called line, which is a string.
You then specify in quotes, very similar to printf, what you expect to see in this string.
And what I'm saying here is I expect to see a decimal number and maybe a character.
And we'll see why this is the case in just a moment.
And it turns out that this notation is now reminiscent of stuff we started talking about
just over a week ago.
What is &n and &c doing for us here? >>[student] Address of n and address of c.
Yeah. It's giving me the address of n and address of c. Why is that important?
You know that with functions in C, you can always return a value or no value at all.
You can return an int, a string, a float, a char, whatever, or you can return void,
but you can only return one thing maximally.
But here we want sscanf to return me maybe an int, a decimal number,
and also a char, and I'll explain why the char in a moment.
You effectively want sscanf to return two things, but that's just not possible in C.
You can work around that by passing in two addresses
because as soon as you hand a function two addresses,
what can that function do with them? >>[student] Write to those addresses.
It can write to those addresses.
You can use the star operation and go there, to each of those addresses.
It's sort of this back-door mechanism but very common for changing the values of variables
more than just one place--in this case, two.
Now notice I'm checking for == 1 and then returning n if that does, in fact, evaluate to true.
So what's going on? Technically, all we really want to happen in GetInt is this.
We want to parse, so to speak, we want to read the string--quote-unquote 123--
and if it looks like there's a number there, what we're telling sscanf to do
is put that number--123--in this variable n for me.
So why then did I actually have this as well?
What is the role of sscanf saying you might also get a character here?
[inaudible student response] >>A decimal point actually could work.
Let's hold that thought for a moment. What else?
[student] It could be NULL. >>Good thought. It could be the null character.
It's actually not in this case. Yeah. >>[student] ASCII.
ASCII. Or let me generalize even further.
The %c there is just for error checking.
We don't want there to be a character after the number,
but what this allows me to do is the following.
It turns out that sscanf, besides storing values in n and c in this example here,
what it also does is it returns the number of variables it put values in.
So if you only type in 123, then only the %d is going to match,
and only n gets stored with a value like 123,
and nothing gets put in c.
C remains a garbage value, so to speak--
garbage because it's never been initialized to some value.
So in that case, sscanf returns 1 because I populated 1 of those pointers,
in which case great, I have an int so I free the line to free up the memory
that GetString actually allocated, and then I return n,
else if you ever wondered where that Retry statement comes from, it comes from right here.
So if, by contrast, I type in 123foo--just some random sequence of text--
sscanf is going to see number, number, number, f,
and it's going to put the 123 in n; it's going to put the f in c and then return 2.
So we have, just using the basic definition of sscanf's behavior, a very simple way--
well, complex at first glance but at the end of the day fairly simple mechanism--
of saying is there an int and if so, is that the only thing that I found?
And the whitespace here is deliberate.
If you read the documentation for sscanf, it tells you that if you include a piece of whitespace
at the beginning or the end, sscanf too will allow the user, for whatever reason,
to hit space bar 123 and that will be legitimate.
You won't yell at the user just because they hit the space bar
at the beginning or the end, which is just a little more user-friendly.
>> Any questions then on GetInt? Yeah. >>[student] What if you just put in a char?
Good question.
What if you just typed in a char like f and hit Enter without ever typing 123?
What do you think the behavior of this line of code would then be?
[inaudible student response]
Yeah, so sscanf can cover that too because in that case, it's not going to fill n or c.
It's going to instead return 0, in which case I'm also catching that scenario
because the expected value I want is 1.
I only want one and only one thing to be filled. Good question.
>> Others? All right.
>> Let's not go through all of the functions in here,
but the one that seems to be perhaps of remaining interest is GetString
because it turns out that GetFloat, GetInt, GetDouble, GetLongLong
all punt a lot of their functionality to GetString.
So let's take a look at how he is implemented here.
This one looks a little complex, but it uses the same fundamentals
that we started talking about last week.
In GetString, which takes no argument as per the void up here
and it returns a string, I apparently am declaring a string called buffer.
I don't really know what that's going to be used for yet, but we'll see.
It looks like capacity is by default 0.
Not quite sure where this is going, not sure what n is going to be used for yet,
but now it's getting a little more interesting.
In line 243, we declare an int, c.
This is sort of a stupid detail.
A char is 8 bits, and 8 bits can store how many different values? >>[student] 256. >>256.
The problem is if you want to have 256 different ASCII characters, which there are
if you think back--and this is not something to memorize.
But if you think back to that big ASCII chart we had weeks ago,
there were in that case 128 or 256 ASCII characters.
We used all the patterns of 0s and 1s up.
That's a problem if you want to be able to detect an error
because if you're already using 256 values for your characters,
you didn't really plan ahead because now you have no way of saying,
this is not a legit character, this is some erroneous message.
So what the world does is they use the next biggest value, something like an int,
so that you have a crazy number of bits, 32, for 4 billion possible values
so that you can simply end up using essentially 257 of them,
1 of which has some special meaning as an error.
>> So let's see how this works.
In line 246, I have this big while loop that is calling fgetc,
f meaning file, so getc, and then stdin.
It turns out this is just the more precise way of saying read input from the keyboard.
Standard input means keyboard, standard output means screen,
and standard error, which we'll see in pset4, means the screen
but a special part of the screen so that it's not conflated with actual output
that you intended to print. But more on that in the future.
So fgetc just means read one character from the keyboard and store it where?
Store it in c.
And then check--so I'm just using some Boolean conjunctions here--
check that it doesn't equal--\n, so the user has hit Enter, we want to stop at that point,
end of the loop--and we also want to check for the special constant EOF,
which if you know or guess, what does it stand for? >>[student] End of file. >>End of file.
This is kind of nonsensical because if I'm typing at the keyboard,
there's really no file involved in this,
but this is just sort of the generic term used to mean
that nothing else is coming from the human's fingers.
EOF--end of file.
As an aside, if you've ever hit Control D at your keyboard, not that you would have yet--
you've hit Control C--Control D sends this special constant called EOF.
So now we just have some dynamic memory allocation.
>> So if (n + 1 > capacity). Now I'll explain n.
N is just how many bytes are currently in the buffer,
the string that you're currently building up from the user.
If you have more characters in your buffer than you have capacity in the buffer,
intuitively what we need to do then is allocate more capacity.
So I'm going to skim over some of the arithmetic here and focus only on this function here.
You know what malloc is or are at least generally familiar.
Take a guess what realloc does. >>[student] Adds memory.
It's not quite adding memory. It reallocates memory as follows.
If there's still room at the end of the string to give you more of that memory
than it originally gives you, then you'll get that additional memory.
So you can just keep putting the string's characters back to back to back to back.
But if that's not the case because you waited too long
and something random got plopped in memory there
but there's extra memory down here, that's okay.
Realloc is going to do all the heavy lifting for you,
move the string you've read in thus far from here, put it down there,
and then give you some more runway at that point.
>> So with a wave of the hand, let me say that what GetString is doing
is it's starting with a small buffer, maybe one single character,
and if the user types in two characters, GetString ends up calling realloc and says
one character wasn't enough; give me two characters.
Then if you read through the logic of the loop, it's going to say
the user typed in 3 characters; give me now not 2 but 4 characters,
then give me 8, then give me 16 and 32.
The fact that I'm doubling the capacity each time
means that the buffer is not going to grow slowly, it's going to grow super fast.
And what might be the advantage of that?
Why am I doubling the size of the buffer
even though the user might just need one extra character from the keyboard?
[inaudible student response] >>What's that? >>[student] You don't have to grow it as often.
Exactly. You don't have to grow it as often.
And this is just kind of you're hedging your bets here,
the idea being that you don't want to call realloc a lot because it tends to be slow.
Any time you ask the operating system for memory,
as you'll soon see in a future problem set, it tends to take some time.
So minimizing that amount of time, even if you're wasting some space,
tends to be a good thing.
>> But if we read through the final part of GetString here--
and again understanding every single line here is not so important today--
notice that it eventually calls malloc again
and it allocates exactly as many bytes as it needs for the string
and then throws away by calling free the excessively large buffer
if it indeed got doubled too many times.
So in short, that's how GetString has been working all this time.
All it does is read one character at a time again and again and again,
and every time it needs some additional memory, it asks the operating system for it
by calling realloc.
>> Any questions? All right.
>> An attack.
Now that we understand pointers or at least are increasingly familiar with pointers,
let's consider how the whole world starts to collapse
if you don't quite defend against adversarial users,
people who are trying to hack into your system,
people who are trying to steal your software by circumventing some registration code
that they might otherwise have to type in.
>> Take a look at this example here, which is just C code that has a function main at the bottom
that calls a function foo. And what is it passing to foo?
[student] A single argument. >>[Malan] A single argument.
So argv[1], which means the first word that the user typed at the command line
after a.out or whatever the program is called.
So foo at the top takes in a char*. But char* is just what? >>[student] A string.
[Malan] A string, so there's nothing new here.
That string is arbitrarily being called bar.
In this line here, char c[12]; in sort of semi-technical English, what is this line doing?
[student] An array of-- >>Array of? >>[student] Characters. >>Characters.
Give me an array of 12 characters. So we might call this a buffer.
It's technically called c, but a buffer in programming just means a bunch of space
that you can put some stuff in.
Then lastly, memcpy we've not used before, but you can probably guess what it does.
It copies memory. What does it do?
It apparently copies bar, its input, into c but only up to the length of bar.
But there's a bug here. >>[student] You need the sizeof character. >>Okay.
Technically, we should really do strlen(bar) * sizeof(char)). That's correct.
But in the worst case here, let's assume that that's--
Okay. Then there's two bugs.
So sizeof(char));
Let's make this a little wider.
So now there's still a bug, which is what? >>[inaudible student response]
Check for what? >>[student] Check for NULL.
We should generally be checking for NULL because bad things happen
when your pointer is NULL because you might end up going there,
and you shouldn't ever be going to NULL by dereferencing it with the star operator.
So that's good. And what else are we doing? Logically, there's a flaw here too.
[student] Check if argc is >= to 2.
So check if argc is >= 2. Okay, so there's three bugs in this program here.
We're now checking if the user actually typed in anything into argv[1]. Good.
So what's the third bug? Yeah. >>[student] C might not be big enough.
Good. We checked one scenario.
We implicitly checked don't copy more memory than would exceed the length of bar.
So if the string the user typed in is 10 characters long,
this is saying only copy 10 characters. And that's okay.
But what if the user typed in a word at the prompt like a 20-character word?
This is saying copy 20 characters from bar into what?
C, otherwise known as our buffer, which means you just wrote data
to 8 byte locations that you do not own,
and you don't own them in the sense that you never allocated them.
So this is what's generally known as the buffer overflow attack or buffer overrun attack.
And it's an attack in the sense that if the user or the program that's calling your function
is doing this maliciously, what actually happens next could actually be quite bad.
>> So let's take a look at this picture here.
This picture represents your stack of memory.
Recall that every time you call a function you get this little frame on the stack
and then another and then another and another.
And thus far, we've just kind of abstracted these as rectangles
either on the board or on the screen here.
But if we zoom in on one of those rectangles, when you call a function foo,
it turns out that there's more on the stack inside of that frame in that rectangle
than just x and y and a and b, like we did talking about swap.
It turns out that there's some lower-level details, among them Return Address.
So it turns out when main calls foo, main has to inform foo
what main's address is in the computer's memory
because otherwise, as soon as foo is done executing, as in this case here,
once you reach this closed curly brace at the end of foo,
how the heck does foo know where the control of the program is supposed to go?
It turns out that the answer to that question is in this red rectangle here.
This represents a pointer, and it's up to the computer to store temporarily
on the so-called stack the address of main so that as soon as foo is done executing,
the computer knows where and what line in main to go back to.
Saved Frame pointer relates similarly to this.
Char *bar here represents what?
Now this blue segment here is foo's frame. What is bar?
Bar is just the argument to the foo function.
So now we're back at sort of the familiar picture.
There's more stuff and more distractions on the screen,
but this light blue segment just is what we've been drawing on the chalkboard
for something like swap. That is the frame for foo.
And the only thing in it right now is bar, which is this parameter.
But what else should be in the stack according to this code here?
[student] char c[12]. >>[Malan] char c[12].
We should also see 12 squares of memory allocated to a variable called c,
and indeed we do have that on the screen.
The very top there is c[0], and then the author of this diagram
didn't bother drawing all of the squares, but there are indeed 12 there
because if you look at the bottom right, c[11] if you count from 0 is the 12th such byte.
But here's the problem.
In which direction is c growing?
Sort of top down if it starts at the top and grows to the bottom.
It doesn't look like we left ourselves much runway here at all.
We've kind of painted ourselves into a corner,
and that c[11] is right up against bar, which is right up against Saved Frame pointer,
which is right up against Return Address. There's no more room.
So what's the implication then if you screw up
and you try reading 20 bytes into a 12-byte buffer?
Where are those 8 additional bytes going to go? >>[student] Inside--
Inside everything else, some of which is super important.
And the most important thing, potentially, is the red box there, Return Address,
because suppose that you either accidentally or adversarially overwrite those 4 bytes,
that pointer address, not just with garbage but with a number
that happens to represent an actual address in memory.
What's the implication, logically? >>[student] Function is going to return to a different place.
Exactly.
When foo returns and hits that curly brace, the program is going to proceed
not to return to main, it's going to return to whatever address is in that red box.
>> In the case of circumventing software registration,
what if the address that's being returned to is the function that normally gets called
after you've paid for the software and inputted your registration code?
You can sort of trick the computer into not going here but instead going up here.
Or if you're really clever, an adversary can actually type in at the keyboard, for instance,
not an actual word, not 20 characters, but suppose he or she actually types in
some characters that represent code.
And it's not going to be C code, it's actually going to be the characters
that represent binary machine code, 0s and 1s.
But suppose they're clever enough to do that,
to somehow paste into the GetString prompt something that is essentially compiled code,
and the last 4 bytes overwrite that return address.
And what address does that input do?
It actually stores in this red rectangle the address of the first byte of the buffer.
So you have to be really clever, and this is a lot of trial and error for bad people out there,
but if you can figure out how big this buffer is
such that the last few bytes in the input you provide to the program
happen to be equivalent to the address of the start of your buffer, you can do this.
If we say normally h-e-l-l-o and \0, that's what ends up in the buffer.
But if we're more clever and we fill that buffer with what we'll generically call attack code--
A-A-A, attack, attack, attack--where this is just something that does something bad,
what happens if you're really clever, you might do this.
In the red box here is a sequence of numbers--80, C0, 35, 08.
Notice that that matches the number that's up here.
It's in reverse order, but more on that some other time.
Notice that this return address has been deliberately altered
to equal the address up here, not the address of main.
So if the bad guy is super smart, he or she is going to include in that attack code
something like delete all of the user's files or copy the passwords
or create a user account that I can then log in to--anything at all.
>> And this is both the danger and the power of C.
Because you have access to memory via pointers
and you can therefore write anything you want into a computer's memory,
you can make a computer do anything you want
simply by having it jump around within its own memory space.
And so to this day so many programs and so many websites that are compromised
boil down to people taking advantage of this.
And this might seem like a super sophisticated attack, but it doesn't always start that way.
The reality is that what bad people will typically do is,
whether it's a program at a command line or a GUI program or a website,
you just start providing nonsense.
You type in a really big word into the search field and hit Enter,
and you wait to see if the website crashes
or you wait to see if the program manifests some error message
because if you get lucky as the bad guy and you provide some crazy input
that crashes the program, that means the programmer didn't anticipate your bad behavior,
which means you can probably with enough effort, enough trial and error,
figure out how to wage a more precise attack.
So as much a part of security is not just avoiding these attacks altogether
but detecting them and actually looking at logs
and seeing what crazy inputs have people typed into your website,
what search terms have people typed into your website
in hopes of overflowing some buffer.
And this all boils down to the simple basics of what's an array
and what does it mean to allocate and use memory.
>> Related to that then too is this.
Let's just glance inside of a hard drive yet again.
You recall from a week or two ago that when you drag files to your recycle bin or trash can,
what happens? >>[student] Nothing. >>Absolutely nothing, right?
Eventually if you run low on disk space,
Windows or Mac OS will start deleting files for you.
But if you drag something in there, that is not at all safe.
All your roommate or friend or family member has to do is double click and, voila,
there's all the sketchy files that you tried to delete.
Most of us at least know that you have to right click or Control click
and empty the trash or something like that.
But even then that doesn't quite do the trick
because what happens when you have a file on your hard drive
that represents some Word document or some JPEG, and this represents your hard drive,
and let's say this sliver here represents that file,
and it's composed of a whole bunch of 0s and 1s.
What happens when you not only drag that file to the trash can or recycle bin
but also empty it? Sort of nothing.
It's not absolutely nothing now.
Now it's just nothing because a little something happens in the form of this table.
So there's some kind of database or table inside of a computer's memory
that essentially has one column for files' names and one column for files' location,
where this might be location 123, just a random number.
So we might have something like x.jpeg and location 123.
What happens then when you actually empty your trash?
That goes away.
But what doesn't go away is the 0s and 1s.
>> So what's then the connection to pset4?
Well, with pset4, just because we've accidentally erased the compact flash card
that had all of these photos or just because it by bad luck became corrupted
doesn't mean that the 0s and 1s aren't still there.
Maybe a few of them are lost because something got corrupted
in the sense that some 0s became 1s and 1s became 0s.
Bad things can happen because of buggy software or defective hardware.
But many of those bits, maybe even 100% of them, are still there.
It's just that the computer or the camera doesn't know where JPEG1 started
and where JPEG2 started.
But if you, the programmer, know with a bit of savvy where those JPEGs are
or what they look like so you can analyze the 0s and 1s and say JPEG, JPEG,
you can write a program with essentially just a for or while loop
that recovers each one of those files.
So the lesson then is to start securely erasing your files
if you'd like to avoid this altogether. Yes.
>> [student] How come it says on your computer
that you have more memory than you did before?
Have more memory than you did before-- >>[student] More available memory.
Oh. Good question.
So why then after emptying the trash does your computer tell you
that you have more free space than you did before?
In a nutshell, because it's lying.
More technically, you do have more space because now you have said
you can put other stuff where that file once was.
But that doesn't mean the bits are going away,
and that doesn't mean the bits are being changed to all 0s, for instance,
for your protection.
So by contrast, if you securely erase files or physically destroy the device,
that really is the only way sometimes around that.
>> So why don't we leave on that semi-scary note, and we will see you on Monday.
[applause]
>> [CS50.TV]