[WEEK 5]
[David J. Malan, Harvard University]
[This is CS50.] [CS50.TV]
[Woman] He's lying; about what, I don't know.
[Man] So what do we know?
[Woman] That at 9:15, Ray Santoya was at the ATM.
[Man] So the question is, what was he doing at 9:16?
[Woman] Shooting the 9 mm at something.
Maybe he saw the sniper.
[Man] Or he was working with him.
[Woman] Wait. Go back one.
[Man] What do you see?
[♫Suspenseful music♫]
[Woman] Bring his face up. Full screen.
[Man] His glasses. >>There's a reflection.
[♫Suspenseful music♫]
[Man] That's the Nuevita's baseball team. That's their logo.
[Woman] And he's talking to whoever's wearing that jacket.
>> [David Malan] So, this is CS50 week 5, and today we ruin a bit of television and movie for you.
So whenever you're watching a show like this one here,
and the cops say "Can you clean that up?" or "Enhance,"
there is no enhance in the real world.
In fact, what you really get is a little something like this.
I've pulled up one of the staff photos from the page.
This is a program called Photoshop. This is 1 of 2 Bowdens,
1 of 3 Bowdens actually, today, because we have Mrs. Bowden here as well, with Rob and Paul.
But here is Rob on the screen, and if we zoom in on that glint he's always had in his eye,
what you actually see is that what you see is what you get.
This is "enhanced," so "CSI" have it a bit wrong.
There's one other clip, if we can pick on "CSI" just a little bit longer.
This one is a nice phrase to utter henceforth if you want to
sound technical with your friends when, really, you're saying absolutely nothing.
>> [Man] For weeks I've been investigating the Cabby Killer murders
with a certain morbid fascination.
[Woman #1] This is in real time.
[Woman #2] I'll create a GUI interface using Visual Basic, see if I can track an IP address.
>> [Malan] So audio out of sync aside, creating a GUI interface using Visual Basic
to track an IP address is complete nonsense.
These days you wouldn't use Visual Basic,
there's no need for a GUI, and IP address was a technically accurate term.
So keep an eye out for these, and one of my favorites:
This one's a little more arcane, because you need to know a different language.
There's a language called Objective-C, which is a superset of C.
Which means it's C plus some additional features, among them object-oriented programming.
And this is the language that Apple has popularized for iOS programming.
And so here's a clip from a different show altogether, from "Numbers,"
that if you actually look closely on your TiVo and pause at the right moment,
you'll see that what they're looking at is not quite what is being described.
And let me try a different audio connector here and see if we can't
keep the audio in sync this time.
I give you "Numbers."
>> [Man #1] It's a 32-bit IPv4 address.
[Man #2] IP, that's the Internet. >>Private network. It's Anita's private network.
[Malan] Okay. This is Objective-C, and it's for some kid's coloring program,
as you can perhaps infer from the name of the variable there.
So that, then, was "Numbers." So today and this week we introduce
a little bit of the world of forensics and the context in the problems therefore.
Today will be an abbreviated lecture because there's a special event in here
afterward, 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 MITs new online initiative for open courseware
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 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,
not quite the best student/teacher ratio once we hit 80,000 other students.
So 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,
and you'll be able to run a command, check 50,
on your own pset, and you'll get some feedback as to whether your program is
correct or incorrect according to various design specifications that we have provided.
So more on that and the problem set specification and
the CS50x classmates will be using this as well.
>> So problem set 4 is all about forensics.
And this piece was inspired by some real-life stuff,
whereby when I was in graduate school, I interned for a while with
the Middlesex County's District Attorney's Office doing forensic work
with their lead forensic investigator, and what this amounted to
is, I think I mentioned a few week's 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; turns out that not that many people
write an email saying "I did it."
So quite often these forensics 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 pset 4 a bit of graphics.
So 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.
Now, in the case of Rob's face, there's all sorts of colors,
and we started to see the individual dots, otherwide 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, well, 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 would 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 the video will be online, as usual, tomorrow.
We'll also introduce you to another file format.
So 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 blue sky,
that was typically a BMP, or bitmap image, and bitmaps
are fun for us because they have a bit more complexity.
It's not quite as simple as this grid of 0's and 1's;
instead, you have things like a header at the start of a file.
So in other words, inside a .bmp file is a whole bunch of 0's and 1's,
but there's some additional 0's and 1's in there.
And it turns out that what we've probably taken for granted for years,
file formats like .doc or .xls or .mp3 or .mp4,
whatever the file formats that you're familiar with.
Well, 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 0's and 1's
and maybe those 0's and 1's represent a,b,c, through ASCII or the like,
but through the end of the day, it's just 0's and 1's.
>> 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's going to be some cryptically named variable called bfType,
which just stands for bitmap file type; what type of bitmap file this is.
You can infer, perhaps, from the second row that offset 2, byte number 2,
has a pattern of 0's and 1's 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 line or 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, the parents in the room might recall some of the earliest projectors.
These days, you just see 1 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 the 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 0's and 1's,
figure out which chunks of 0's and 1's 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, 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 0's and 1's
off of that card for you, saved them all in 1 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 0's and 1's.
So using a while loop or a for loop or similar,
you can iterate over all the 0's and 1's in this forensic image
and every time you see the special pattern that's defined in the problem set's specification,
you can assume, 'Oh, 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, 'Ooh! 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 pset 4 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.
That's what's on the horizon.
>> Quiz 0, behind us. Realize, per my email, that invariably there's folks
who are both happy, sort of neutral, and sad around quiz 0 time.
And please do reach out to me, the head TFs, 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? Good job.
What's the CS50 library? Yeah? [Student answers, unintelligible]
>>Okay, good. So it's a prewritten set of code that we, the staff, wrote,
we provide to you, to provide some common functionalities.
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.
So we're going to start to take away a "string" from you,
which, recall, was just a synonym for what actual data type? char *.
So for parents, that was probably--that's good, so 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 sharp including for weeks.
>> But let's actually see what's inside of this.
So the top of the file in blue is just a whole bunch of comments,
warranty information and licencing. 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 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.
So notice at the top here, that the CS50.h file includes a whole bunch of header files.
Now, most of these we haven't seen before, but one is
familiar; which of these have we seen, albeit briefly, thus far?
Yeah, standard libraries. Stdlib.h has malloc,
so 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.
So we have, for weeks, been including standard bool.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.
>> Now, if we scroll down further, here is our definition of a string.
It turns out, as we've said before, that where this * 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 * 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 say, GetInt,
because we used that, perhaps, before anything else this semester.
And here is GetInt. This is what?
This is the prototype. So 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 sharp 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 sharp include mechanism
that essentially copies and pastes this file into your own.
Now, here is some fairly detailed documentation.
>> We've pretty much taken for granted that GetInt gets an int,
but it turns out there's some corner cases, right?
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? Well, ideally, it's predictable.
So in this case, if you actually read the fine print,
you'll 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?
It's a constant, so 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,
negative 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 negative 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 "2, 3, 4. . . "
of really big number, where you generalize instead as a constant.
So really, if you were being anal the past few weeks,
anytime you call 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.
>> Well, let's now turn in to the .c files.
The C file has existed in the appliance for some time,
and, in fact, the appliance has it precompiled 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.
But let's scroll down now to GetInt, and see how GetInt has been working all this time.
So 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 and 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.
So let's see how this works. Well, 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 this special keyword, NULL?
If something goes wrong. What could go wrong when you call something like GetString?
Yeah? [Student answer, unintelligible] >>Yeah. So 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.
More characters than the computer even has RAM.
Well, 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 go back and read its documentation, does, in fact, return NULL.
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.
So let's scroll down to where the int is actually GotInt.
>> So if I scroll down a bit further, in line 170 we have a comment above these lines.
So we declare, in 172, an int n and a char c, and then this new function
which some of you have stumbled across before, but sscanf.
This stands for string scan f.
In other words, give me a string and I will scan it for pieces of information of interest.
So what does that mean? Well, suppose that I type in, literally, 1 2 3 at the keyboard,
and then hit enter. What is the data type of 1 2 3 when returned by GetString?
It's obviously a string, right? I got a string, so 1 2 3 is really "1 2 3"
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,
1 2 3 \0, and somehow convert it to an actual integer.
Now, you could figure out how to do this.
If you think back to pset 2, you presumably got a little comfortable
with Caesar or vigenere so you can iterate over a string,
you can convert chars to ints with pick. That'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 do you expect to see in this string?
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.
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 answers, unintelligible]
>>Yeah. It's giving me the address of n and address of c.
Now, why is that important? Well, 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 1 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.
So you effectively want f to return 2 things; that's just not possible in C.
So you can work around that by passing in 2 addresses,
because as soon as you hand a function 2 addresses, what can that function do with them?
It can write to those addresses. You can use the * operation and "go there" to each of those addresses.
It's sort of this backdoor mechanism, but very common for changing the values of variables
in more than just 1 place, in this case 2.
Now, notice I'm checking for == to1, and then returning n if that does, in fact, evaluate to true.
So what's going on? Well, technically, all we really want to happen in GetInt is this.
We want to parse, so to speak; we want to read the string
"1 2 3" and if it looks like there's a number there,
what we're telling sscanf to do is put that number, 1 2 3, in this variable n for me.
Why, then, did I have this as well?
What is the role of also saying, sscanf, you might also get a character here.
[Student speaking, unintelligible] >>Not--a decimal point could work.
Let's hold that thought for a moment. What else?
[Student, unintelligible] >>So, good thought, it could be the NULL character.
It's actually not, in this case. Yeah? [Student, unintelligible]
>> >> ASCII. Or, let me generalize even further.
The %c there is just for error-checking.
We don't want there to be 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 1 2 3, then only the %d is going to match
and only n gets stored with a value like 1 2 3 and nothing gets put in c;
c remains a garbage value, so to speak.
Garbage because it's never been initialized as some value.
So in that case, sscanf returns 1, because I populated one 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, comes from right here.
If, by contrast, I type in 1 2 3 foo,
just some random sequence of text, sscanf is going to see,
ooh, number, ooh, number, ooh, number, ooh--f.
And it's going to put the 1 2 3 in n.
It's going to put the f in c, and then return 2.
So we have, just using the basic definition of scanf'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 white space here is deliberate. If you read the documentation for sscanf,
it tells you that if you include a piece of white space at the beginning or the end,
sscanf too will allow the user, for whatever reason, to hit spacebar 1 2 3, and that will be legitimate.
It won't yell at the user just because they hit the spacebar at the beginning or the end,
which is just a little more user-friendly.
>> Any questions, then, on GetInts? Yeah?
[Student question, unintelligible]
>>Good question. What if you just typed in a char, like f, and hit enter
without ever typing 1 2 3; what do you think the behavior of this line of code would then be?
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 1, and only 1 thing to be filled. Good question. Others?
>> All right, so 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. So in GetString,
which takes no argument as per the void up here,
and it returns a string; so I am declaring a string called buffer.
I don't really know what that's going to be used for yet, but we'll see.
Looks like capacity is, by default, 0; not quite sure where this is going.
Not sure what n's going to be used for yet.
But now it's getting a little more interesting, so 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?
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 0's and 1's 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, getc, and then stdin.
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 pset 4, 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?
End of file. So 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.
But 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.
I'm going to skim over some of the arithmetic here
and focus only on this function here.
You know what malloc is, or at least generally familiar.
Take a guess what realloc does. [Student answer, unintelligible]
>>Yeah. And 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 putting the strings 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 into 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 1 single character,
and if the user types in 2 characters, GetString ends up
calling realloc and says, 'Ooh, 1 character wasn't enough.
Give me 2 characters.' Then if you read through the logic of the loop,
it's going to say, 'Ooh, 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 1 extra character from the keyboard?
[Student answer, unintelligible]. >>What's that?
Exactly. You don't have to grow it as often.
And this is just kind of a--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.
But 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.
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.
>>Single argument. So argv[1], which means the first word 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?
String. There's nothing new here, and 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?
Array of--? 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? Well, it apparently copies bar, its input, into c,
but only up to the length of bar.
But there's a bug here.
Okay, so technically we should really do strlen(bar) x sizeof(char), that's correct.
But in the worst case here, let's assume that that's--so, okay.
Then there's 2 bugs. So sizeof(char), all right, let's make this a little wider.
So now there's still a bug, which is what?
[Student answer, unintelligible] >>Check for what? Okay, so we should 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 * operator.
So that's good, and what else are we doing? Logically there's a flaw here too.
[Student answer, unintelligible]
>>So check if argc ≥ 2?
Okay, so there's 3 bugs in this program here.
We're not checking if the user actually typed in anything into argv[1], good.
So what's the third bug? Yeah?
[Student answer, unintelligible] >>Good.
So 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 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 be quite bad.
>> Let's take a look at this picture here.
This picture represents your stack of memory.
And recall that every time you call a function,
you get this little frame on the stack and then another and then another and then another.
And thus far we've just kind of abstracted these away as rectangles
either there 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 and that rectangle
than just x and y and a and b, like we did talking about swap.
It turns out that there are 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 close curly brace at the end of foo,
how the heck does foo know where control of the program is supposed to go?
It turns out that the answer to that question is in that 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?
Well, now this blue segment here is foo's frame, what is bar?
Okay, so bar is just the argument to the foo function.
>> So now we're back at the familiar picture.
There's more stuff and more distractions on the screen
but this light blue segment 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?
Char c[12]. So 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 12 such bytes.
But here's the problem: In which direction is c growing?
Sort of top down, right? If it starts at the top and grows to the bottom,
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 stack frame pointer,
which is right up against the 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?
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 are 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 implicaiton, logically?
[Student answers, unintelligible] >>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.
>> Now, in the case of circumventing software registration,
what is 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 could 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
types in some characters that represent code?
And it's not going to be C code, it's going to be the characters
that represent binary machine codes, 0's and 1's.
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 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 that 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, A: Attack, attack, attack, attack, where this is just something that does something bad.
Well, what happens if you're really clever, you might do this:
In the red box here is a sequence of numbers: 80, CO, 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 log into.'
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,
is 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?
And related to that, too, is this.
>> So let's just glance inside of a hard drive yet again.
So you recall from a week or two ago that when you drag files
to your recycle bin or trash can, what happens?
[Student] Nothing. >>Yeah, absolutely nothing. 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, then it's not at all safe.
All your roomate, friend or family member has to do is double click, and voila.
There's all the sketchy files that you tried to delete.
So 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 0's and 1's.
What happens when you not only drag that file to the trashcan 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 1 column for files names,
and 1 column for file's location, where this might be location 123, just a random number.
So we might have something like x.jpg, and location 123.
And what happens then, when you empty your trash?
That goes away. But what doesn't go away is the 0's and 1's.
>> So what's, then, the connection to pset 4?
Well, with pset 4, 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 0's and 1's aren't still there.
Maybe a few of them are lost because something got corrupted
in the sense that some 0's became 1's and 1's became 0's.
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 JPEG 1 started
and where JPEG 2 started, but if you, the programmer,
know, with a bit of savvy, where those JPEGs are or what they look like,
you can analyze the 0's and 1's and say, 'Ooh. JPEG. Ooh, JPEG.'
You can write a program with essentially just a for or while loop
that recovers each and every 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 question, unintelligible]
>>Have more memory than you did before--
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 all 0's, for instance, for your protection.
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.
CS50.TV