>> David Malan: All right, welcome back to CS50!
This is week five, so in problem set two, you'll recall that some
of your classmates tackled the so-called hacker edition,
and that hacker edition had them tackle a number
of encrypted passwords,
which looked a little something like this.
So, long story short, if you didn't actually read this PDF
at the time, this was the hacker edition.
Passwords on the typical Linux system are stored
in an encrypted form, so you have essentially this format
in a file called XE Password Etcetera/Password.
Julius would be the username, colon,
and then some cryptic-looking string would be the
encrypted password.
And do you mind, Barry, taking my voice down a little bit?
There's a bit of an echo up here.
Much better.
So, these students, who tackled the hacker edition,
needed to decipher, needed to crack those passwords; but,
unfortunately, the routine that's used
in a typical Linux system
to encrypt passwords is a one-way function,
which means it's relatively easy and relatively fast to take
in plaintext and generate cipher text,
but you can't actually reverse the process.
So, as I mentioned a few weeks ago,
if you've ever lost a password to a typical website
or to your FAS account, odds are you might've gotten annoyed
at the text support person, because they insisted,
"I can't tell you what your password is,"
but they can change it,
and that's because of this mathematical property that's
generally used for passwords.
They're normally known as a one-way hash.
And as the name implies, you can only encrypt
in one direction; you can't decrypt.
So, if you can't decrypt passwords in this way,
how in the world are all of us logging in to FAS and logging
in to Facebook and other such sites every day of the week?
How is it that these sites are storing our passwords encrypted,
and yet they're still somehow checking that what I type in,
in plaintext, matches my password?
So, in other words, if you can't decrypt the cipher text
to then compare the plaintext I initially gave them,
when I created my account, and the plaintext I just typed in,
when visiting Facebook.com or equivalent,
how do you actually compare what I typed in
and what they know my password to be?
Yeah?
>> Just encrypt what [inaudible].
>> David: Just what?
>> Encrypt what --
>> David: Yeah, just encrypt what I just typed in.
So, in other words, what a typical website
or server does these days is, again, it encrypts your password
when you create your account and stores it in a crazy format
like this; but, subsequently, when you log in,
the server simply re-encrypts whatever you just typed in,
using the same algorithm.
And then if the two cipher texts match,
does it actually let you pass.
But the curious thing is, because of the mathematics
of a lot of these implementations,
there is a probability, though very, very low,
that you could type in one word, and it would encrypt
to some cipher text, and you could type in another word,
a different word, but it might very well encrypt
to that same cipher text; in other words,
you might very well be able to login
to some accounts you guys have, using any number of passwords,
but the probability of that is very low, and the probability
of figuring out what other words might hash, so to speak,
to the same value is itself very low.
So, a number of our students, who are more comfortable, did,
in fact, determine that Julius' password was just 13.
The clever, or those who like stupid jokes might understand
what the reference there is.
Julius Caesar, you know, 13.
Okay. President Scroob, of course,
in the Spaceballs, Smith hack.
You've got to make fun of me when I do something like this.
There we go.
All right, President Scroob had a password of 12345.
That was the second password these guys were tasked
with figuring out.
W. Brandus Voice, this is actually a reference to a movie
that many of you probably haven't seen,
but the movie Sneakers, where a guy authenticates himself
as saying, "My voice is my password," a little example
of using vocal algorithmics.
That was his there.
But notice what was important about voice was
that it's just an English word.
So any hacker students
that actually used an English dictionary to try
to crack our passwords probably would've gotten this one.
Baravelli, which is a reference to an old Marx Brothers film.
Swordfish, also a word that's probably in the dictionary.
But then it got a little harder,
so you may remember Mr. Blaise Visionaire [phonetic] of France,
who we used Foobar as our keyword.
A little harder.
It's probably not in most dictionaries,
let alone all capitalized.
G. Costanza.
Remember? Those familiar might recall
that this was his ATM code, Bosco, a little chocolaty drink.
And then Malan, I don't believe, was gotten by anyone,
but that's because it was, in fact, rather difficult
to crack and was this.
For those who don't understand what the reference is,
just Goggle FTW and 111, and you'll see
such stupid illusions as those.
So, I finally found a video that's actually educational
in nature.
[laughter] So, you might not think it,
but this thing here actually comes to us
by a very well-known professor, Nick Parlante
at Stanford University.
That's actually very well-known
for its computer science program.
So, this isn't a joke, but this is actually one
of the most compelling ways I have, at least,
seen in clay form to convey the idea
of pointers and dereferencing.
So, this is, for many students, a challenging topic.
It certainly was for me years ago; but, frankly,
we've just kind of taken ourselves
down a notch with Binky here.
Might hopefully elucidate what might otherwise, in C syntax,
be a fairly cryptic topic.
So, allow me to full screen, and allow me
to give us this short three-minute film.
Here we are.
>> Nick Parlante: Hey, Binky.
Wake up. It's time for pointer fun.
>> Binky: What's that?
Learn about pointers?
Oh, goody!
>> David: Mind you, this is a Stanford professor playing
with clay, doing the voiceover here on camera.
[laughter]
>> Nick: Well, to get started, I guess we're going
to need a couple of pointers.
>> Binky: Okay.
This code allocates two pointers,
which can point to integers.
>> Nick: Okay, well, I see the two pointers,
but they don't seem to be pointing to anything.
>> Binky That's right.
Initially, pointers don't point to anything.
The things they point to are called pointees,
and setting them up is a separate step.
>> Nick: Oh, right, right.
I knew that.
The pointees are separate.
So, how do you allocate a pointee?
>> Binky: Okay, well, this code allocates a new integer pointee,
and this part sets X to point to it.
>> Nick: Hey, that looks better.
So, make it do something.
>> Binky: Okay, I'll dereference the pointer X
to store the number 42 into its pointee.
For this trick, I'll need my magic wand of dereferencing.
>> Nick: Your magic wand of dereferencing?
That's great.
>> Binky: This is what the code looks like.
I'll just set up the number and-- [pop]
>> Nick: Hey, look, there it goes.
So, doing a dereference on X follows the arrow
to access its pointee, in this case, to store 42 in there.
Hey, try using it to store the number 13
through the other pointer, Y.
>> Binky: Okay.
I'll just go over here to Y, and get the number 13 set up,
and then take the wand of dereferencing, and just...
[buzz] Oh!
>> Nick: Oh, hey, that didn't work.
Say, Binky, I don't think dereferencing Y is a good idea,
'cause setting up the pointee is a separate step,
and I don't think we ever did it.
>> Binky: Mm, good point.
>> Nick: Yeah, we allocated the pointer Y, but we never set it
to point to a pointee.
>> Binky: Mm, very observant.
>> Nick: Hey, you're looking good there, Binky.
Can you fix it so that Y points to the same pointee as X?
>> Binky: Sure, I'll use my magic wand
of pointer assignment.
>> Nick: Is that going to be a problem like before?
>> Binky: No, this doesn't touch the pointees.
It just changes one pointer to point
to the same thing as another.
>> Nick: Oh, I see.
Now Y points to the same place as X. So, wait.
Now Y is fixed.
It has a pointee, so you can try the wand of dereferencing again.
So, send the 13 over.
>> Binky: Oh, okay.
Here goes.
>> Nick: Hey, look at that.
Now dereferencing works on Y.
And because the pointers are sharing
that one pointee, they both see the 13.
>> Binky: Yeah, sharing, whatever.
So, are we going to switch places now?
>> Nick: Oh, look.
We're out of time.
>> Binky: But--
>> Nick: Just remember the three pointer rules.
Number one, the basic structure is that you have a pointer,
and it points over to a pointee, but the pointer
and pointee are separate, and the common error is to set
up a pointer, but to forget to give it a pointee.
Number two, pointer dereferencing starts
at the pointer and follows its arrow
over to access its pointee.
As we all know, this only works if there is a pointee,
which kind of gets back to rule number one.
Number three, pointer assignment takes one pointer and changes it
to point to the same pointee as another pointer.
So, after the assignment,
the two pointers will point to the same pointee.
Sometimes that's called sharing.
And that's all there is to it, really.
Bye-bye now.
>> David: So if you actually still struggle with pointers
at any point this semester, watch that video,
and hopefully all your troubles will go away.
So, I can't imagine, frankly, how long it took him to make it,
because, if you notice, throughout the video, I mean,
he was changing like the eyeballs' locations
for almost every frame of the video.
So that's an overnight project there, at least.
I wanted to show you this demo, too.
So, this is made by one of our own teaching fellows, Phil,
who was a student in the course last year, who goes,
even though it's only October here,
final projects will soon upon us,
or at least thoughts about final projects.
And just as a teaser now, you'll get more formal documentation
of this in the weeks to come.
The final project in this course really is meant
to be its culmination, where you guys can take your newfound
savvy and comfort, with programming in any
of the languages we cover or don't cover in the course
and design some piece of software of your very own.
So, what Phil did, actually, for fun, just before term started,
was started playing with a fairly large dataset,
that of the course catalog.
So, he wrote, at the time, what's called a screen scraper,
which is a fairly annoying but sometimes effective approach
to getting data from some source
that doesn't necessarily want you to have that data.
So, the registrar's catalog is all HTML pages, all web pages,
but they fortunately follow a standard format.
So, if you wrote a program that essentially crawled
to the registrar's website, much like Google
and other search engines crawl the web, and then read
into a database of his own, all of the information
about this course and that course.
And then what he did was he taught himself a library called
Flair, that allows him to write software in Adobe Flash,
if you're familiar with the Flash format.
And what's neat about Flash is
that you can do fairly sophisticated animations
by writing in a language called ActionScript.
So what this here is, is version 0.9 of a visualization
of the course catalog for all computer science courses.
And as is no accident, perhaps, he has 50 kind of interconnects,
all of these guys here at the center.
And if you hover over CS50, what the edges
in this graph tell you is where you can go after CS50,
for what courses 50 is a prerequisite,
and you can follow the links for all these other courses
and get the descriptions on the side.
And I point this out, because Phil did not, at the time,
so far as I know, he had not used this library before.
He simply Googled.
He read up on it.
He took a little bit of input from the course,
as to what would be neat,
and then he started making what's starting
out to be a really neat visualization.
So, his hope is to do that for the rest of the course catalog.
And this is just to seed your minds with just some random,
crazy ideas that might interest you, whether it's this,
doing something with shuttles, doing something
with dining hall menus.
The really neat thing, once you have these programming chops,
is that you can start to do interesting things with data,
and that data, again, may be shuttle schedules.
It may be a course catalog.
But there's so much interesting stuff out there, and soon,
if not already, you will have the ability
to actually manipulate that, and bend it to your will,
and make interesting applications.
So, speaking of applications, this week is about Sudoku.
This is our logo for the week, made by our own Yuhki Yamashita.
I double-checked, when he handed me this graphic,
with another Japanese-speaking friend,
that I wasn't putting something incredibly offensive on all
of our documents for the week.
So, this isn't that consistent with Sudoku in some form,
but with Sudoku, those of you who have tackled it already,
you know that it uses this library called ncurses,
a graphical library.
And we're not talking graphics in the Mac OS or Windows sense.
It's still fairly primitive stuff within the confines
of this terminal window.
But those of you who might have been taking to heart our advice
that you use GDB anytime you run into a problem,
might've realized that once you have a graphical user interface
between you and your code, it's kind of hard to use GDB and step
through your program, if you've got a big game board right
in the middle of the screen.
So, Glen Holloway [assumed spelling], one of our sysadmins,
actually posted last night
on the bulletin board a little trick
that I thought I'd show you real quickly here.
What's really neat is if you connect a nice FAS
in two windows simultaneously, now, there is a probability
that you'll actually end up connecting
to two different servers that FAS owns.
Nice thought, FAS, even though we've been calling it one
server, is actually a cluster of servers,
so you can actually get pseudo randomly sent
to one machine or the other.
So look to the bulletin board and help at CS50.net as to how
to mitigate this, if you don't find that this is working.
But I've done that.
I've connected to two machines.
I'm going to do a quick sanity check.
I'm going to type post name, and what I see there is
that the nice machine that I'm connected
to actually has a name of Ice 2.
And if I do host name in this other window,
I also have Ice 2 there.
So there's Ice 1, Ice 2, Ice 3.
And as an aside, if you find that you're
on the wrong machine, you can actually just type SSH
or username@ice2.fas.harbor.edu, and that will make sure
that you connect from this machine to the right one.
But the endgame, ultimately, is just to make sure you're
on the same machine physically, and I am.
And what I'm going to do now is this.
I'm going to run Sudoku after compiling it here.
I'm going to go ahead and run Sudoku
and then using the newbie level, so I'm just going
to pick a newbie game, but I'm going to type an ampersand
at the end of the command.
If I don't type an ampersand, I get Sudoku.
Filling my screen, doing the nice little graphics
that it ships with and your distribution code.
But if I do an ampersand, nothing seems to happen.
So, in a Linux or a Mac OS environment,
putting an ampersand at the end
of your commands actually backgrounds the application,
which means it is, in fact, running, and I can see this
by typing PS, which shows you the process list.
A process list, in computer speak,
is just a running program.
If you've ever looked at your Task Manager in Windows
or your Activity Monitor in Mac OS, it's the same thing,
albeit in text form here.
So, I'm running a few things.
One is called Sudoku.
One is called PS, because I literally just ran that,
so PS notices that it's self-running.
And then, out of curiosity, what is TCSH, T-C-S-H?
TCSH? So, this is your shell.
So, when we talked about your prompts or your blinking prompt,
that's actually a program, a program that takes input.
The input it takes is whatever you type
in at the command prompt and hit enter.
So, know, just FYI, there's a lot of shells out there.
There's TCSH.
There's CSH.
There's KSH.
There's the born shell.
There's a whole bunch of shells that people have written
over the years, most of which behave similarly.
But if you ever, after CS50,
connect to what you're told is a Linux or Unix machine,
and things don't quite seem to be working as expected,
it probably just means the shell is slightly different.
So, basics like LS will still work.
CD will still work, but there might be some other differences.
But don't be startled by those.
But what's important here is the following.
When I just run this command, I backgrounded the application,
and what I'm told is that the process I'm running,
the first one I backgrounded, has a PID, process ID of 6373.
This is just a unique number that Linux, or Windows,
or Mac OS assigned to this program
so that it can keep track of it in memory.
But this is useful, because if I now type FG, for foreground,
that's going to put things in the front of my screen,
and it's going to let the program run as usual.
So now I'm going to go to my second window here,
and I'm going to run GDB on Sudoku on 6373.
So a new little trick.
At the command prompt, I'm going to type the name of the program,
but also the process ID here, hit enter.
What I'm now at is a prompt, GDB.
There's a whole bunch of stuff
that loaded, but never mind that.
And I'm going to do something like set a breakpoint
in Sudoku.c line 164, which I just so happen
to know is the part of the code, if you've looked at it already,
is where I'm dealing with user input.
So I'm going to hit enter here.
I have a breakpoint, but now I still seem
to have broken the program.
How do I tell the program to just keep running now
until it hits that breakpoint?
Remember continue?
So continue.
Now nothing seems to be happening,
but that's because the program is now running.
If, as you see in the bottom, we have a little menu here:
N for new game, R for restart game.
If I go ahead and type N, notice what happened.
Nothing in the game, but on the right-hand side,
GDB appears to have responded.
So this is actually a really neat trick.
I'm sort of remotely debugging one process
in a separate window altogether.
So now on the right-hand side, I've broken at line 164.
For those who have looked at the distribution code already,
this is the kind of stuff in Sudoku.c
that we've given you this week.
And long story short, at this part of the code, am I sitting
in a loop waiting for user input?
But what's really neat now is
that I still have the game running in the left-hand side.
On the right-hand side, I can do things like print the value
of a variable called g.number, which is discussed
in the PDF, for those unfamiliar.
Apparently, it's 160 right now.
Oh, look at that.
I'm playing the 160th new board at the time, so there is,
in fact, a correspondent.
So, for those of you who have been kind of banging your head
against the wall, struggling with various bugs,
know that relatively easily can you use GDB
in this still interactive format without getting caught
up in the graphical details.
So, courtesy of Glen, this particular trick.
So, if you didn't get all that, just post it as a sticky
on the course's bulletin board,
so you can check the other category
or the P set 4 category there.
So, I'm just going to quit.
I'm just going to quit here, and then voila!
Any questions?
We tricked fast, but we'll recover it
in section, if need be.
Okay, so there's never a more attentive audience
than when you're talking about things
that affect them personally or can get in their way
of their privacy or their security.
So what I thought we'd do-- because this week,
we lay the foundation in terms of concepts
for a specific domain, that of forensics.
So, in a couple of weeks' time,
we'll be distributing problem set five.
Problem set five's theme is, in fact, forensics,
where you're going to have
to implement some digital forensic-type software
to recover, among other things, some accidentally deleted JPEGs.
So, if you see me and a couple of the teaching fellows
on campus this coming week, taking photos,
just keep walking, because that kind
of spoils the scavenger hunt.
In fact, last year, we were kind of trailed, as I recall,
by one student, who was taking notice of where all the hidden,
but-- let's see-- non-obvious,
but identifiable locations on campus were.
So, we'll be on the lookout.
Buffer overflow attacks.
How does this relate?
So, we talked last week about security and bad stuff
that can arise when you manipulate pointers
or ultimately manage your own memory.
And still, today, one of the most common ways
of compromising a program or server is
to exploit someone's mistake with regard to memory.
If that program is written in a language like C or C++,
that means specifically someone screwed up with regard
to a pointer, or someone screwed up with regard to an array.
So what I thought I'd do is make this a little more concrete,
using some really nice visuals that someone put together here
of a very simple program.
So, this program here has a main routine at the bottom.
It has N to ARDC char ** ARDV.
This is the same thing, recall, as saying CHAR*ARDV [],
because we've seen this relation between pointers and arrays,
so that's just another way of saying the same thing.
The only thing this program does when run, apparently,
is call a function called foo, and it passed
to foo the first command line argument,
whatever the user typed after the program's name.
What does foo do?
Well, it apparently takes a string, aka CHAR*'s input.
It then declares statically on the stack,
because this is a local variable in an array called C.
That array called C has 12 locations,
each of which is a CHAR,
and those locations are all contiguous.
So, this is 12 one byte chunks
of memory back-to-back called C on the stack.
Then there's this function here, which we haven't really used,
but you can infer its role.
Memcpy simply copies memory from a source to a destination.
So, apparently what this function is doing is passing
in to C the value that's in bar, and it's doing this
for how many characters?
Well, however many characters were in bar.
So, in other words, the destination is C. That's
where we want to put a copy of ARDV1.
The string we want to put there is, again, bar,
because that's what we gave this variable's name.
And then the length of bar tells us, tells probably memcpy's
for loop how many characters to actually copy.
But there's a bug in here, as implied by this comment.
When it says no bounds checking, what does that mean?
What are we not checking here?
So the bounds of C, right?
So we've declared C to be of size 12,
and we are doing a sanity check.
We're checking how long bar is,
so that we tell memcpy, you know what?
Only copy the first N characters of bar,
where N equals stir length of bar.
But what's the problem?
What value of string length of bar could cause problems for us?
Any value that's what?
Any value that's greater than 12.
Because if we copy more than 12 bites, that's perfectly fine,
from bar's perspective, because bar has
as many characters as he has.
So, it's fine if we traverse all of those characters,
but if we blindly copy more than 12 characters
into the array called C,
who knows where we're going to be putting them?
We're going to start overlapping something else on the stack,
and that's precisely what a buffer overflow attack is
all about.
So, here's a really nice picture that someone put together.
Actually, if you'd like to read more on this stuff,
the Wikipedia article, at the moment, is really nicely--
really nicely describes this process.
So, notice what we have here, a rectangle very similar
to the one we've been using in class.
At the bottom there, where it says parent routine stack,
so that's like main stack.
So main or any functions down below.
In red is highlighted the return address.
So, we haven't talked about this, but one of the things
that the stack is used for, besides parameters
and besides local variables, is the address of the function
that should be returned to after another function is
done executing.
So, in other words, if main calls foo,
what happens is main's return address, main's address
in memory-- remember the text segment?
Mains address in memory is plopped on top of the stack,
so that the computer, when it's done executing the function foo,
it then checks that lowest level frame, that red bar up there,
and says, "What address should I now return execution to?
Where should I go back to executing?
Because I forget."
It checks that value and, hopefully, that's,
in fact, main's address.
So a smart adversary might recognize this
and might recognize, okay, at the very top of this picture,
we have the start of the array, called C, hence C bracket zero,
and at the bottom right corner
of that rectangle we have C bracket 11.
In other words, the computer has given us 12 bytes from top left
to bottom right there, but where,
according to this picture, if you pass in or try to copy more
than 12 bytes, are we going to start writing?
We're first going to overwrite what value?
>> Bar.
>> David: Bar, because bar is right below C11.
So, as the picture implies, if you try to write to C12, or C13,
or C bracket 14, or anything like that, you're going to start
to go lower and lower into the stack, and so we're going
to start to corrupt or clobber bar's value.
Worse, we might clobber this thing called the saved frame
pointer in green.
This is another detail that the computer uses to remember
where in ram it currently is
and which memory it's actually using.
And worse, if we write so much data into that array,
completely overflowing it,
such that we also overwrite the red return address,
what the adversary can effectively do is trick the
computer into returning to the wrong address completely.
The next function that gets executed is not going
to be main, where it left off, but it could be anywhere in ram.
So, if you have this power now to tell the computer
to trick the computer to go anywhere in memory,
that just begs the question, where do you want them to go?
Well, you probably want, you being the adversary,
you probably want them to go to a location
that has some malicious code, code ideally that you wrote
that maybe circumvents a serial number check,
that maybe circumvents a password check
that does whatever you want this thing to do,
and that's precisely what a buffer overrun does.
So, if you just type in hello, h-e-l-l-o,
and then you get the 0 at the end of it,
that's perfectly safe.
But to be clear, notice that the string fills the stack
from the top on down, because even though we've been drawing
this picture, as though the stack is on the bottom
and the heap is on the top, just because of convention,
notice that it's a little small here, but the black arrow
on the right says memory addresses grow downward.
In other words, in memory, the smaller addresses are on top,
and the larger addresses are on the bottom,
counterintuitive though that may seem,
given how we've been drawing the pictures, but the implication is
that if you plop down H, that does in a low numbered address.
E slightly higher, LLO slightly higher, slightly higher.
If you keep writing well beyond those 12 chars, you're going
to go to a higher and higher memory address,
which pictorially is actually down below,
at which point you will eventually start
to overwrite that return value.
So here's just an example.
If the adversary has just written a bunch of junk,
so represented here by the letter A, the character A,
it's just junk, junk, junk, junk, junk, but then finally
in the red boxes, just because the adversary is lucky or he
or she is particularly adroit with figuring out what he
or she needs to input into the machine,
it turns out that we have a 32-bit integer now
in the red box, so each of those red boxes represents a char,
but if you have four of them, that's an ent, so these types
of decimal values now just represent, collectively,
a 32-bit value, a big number, a 32-bit number.
But because the adversary was smart, he or she realized,
through trial and error or some very clever handiwork,
that if I write this address here, that's going
to trick the computer into executing the code that's
up here, because this address of 80C03508 just so happens to be
up here at the start of this blue block labeled A.
So the implication, if not too long a tale here,
is that if the adversary points some malicious code,
some password circumventing code,
serial number circumventing code, at the top of the stack,
where that first blue A is, and then very intelligently puts
that address down here in the red boxes,
this adversary can trick the computer
into executing their code that they wrote,
that were not actually in the original program.
Now, what can this result in?
Frankly, anything.
If you have the ability to inject arbitrary code
into the computer's memory, you can do anything you want,
and a lot of the time, just crashes the server.
So, if you ever happen to be a webmaster
for some student group, you're trolling through your logs,
just seeing what people are requesting,
very often, you'll see just junk.
You won't see valid URLs being requested.
You'll see a part of a valid URL and a whole bunch of nonsense,
binary data, and that's because one
of the most common approaches to finding mistakes like this,
finding a mistake like this, where I'm failing
to check just how large C is, is just hammer on the machine.
Throw as much data as you can on it, because you know what?
If you actually cause that machine to crash,
probably not your goal, but something interesting is there.
There's some potential to do some bad work,
so that's very often the first approach is just bang
on the thing.
And if it breaks, aha, now you've got a potential target.
So this is a-- there's a more general approach to this.
You don't have to be as precise as this picture implies.
What a lot of people use are these things called NOP sleds.
So, a NOP, N-O-P, is no operation,
and this actually a CPU instruction that's supported
by many CPUs.
That just tells the CPU, for a moment in time,
for a little clock tick, do nothing.
So if you have enough of these, you can actually tell the CPU,
for some number of nanoseconds or the like, do nothing,
do nothing, do nothing, but keep continuing down.
So even though this picture implies that the adversary had
to know precisely where all
of these addresses were, they usually don't.
And so, usually, the code they inject has a whole lot of NOPs
that fills the space, but tells the CPU just keep going,
keep going, keep going until you actually see an instruction
that's not a NOP.
So shell code refers to the code they want to inject.
NOP just means keep going, keep going, keep going.
So it's just a way of kind of filling the space in hopes
that you actually maximize probability
of compromising the machine.
So, if you like this kind of stuff, or want to do this kind
of stuff, CS61 next fall is a course that actually allows you
to dabble in things like this.
In fact, one of the first problem sets is really neat.
It's a ticking time bomb, of sorts,
whereby the professor hands you a program compiled in Linux.
It has a number of password prompts, and you're challenged
to figure out what the passwords are without actually guessing
and without detonating the so-called binary bomb.
In other words, if you type the wrong password in--
it's actually quite clever.
If you type the wrong password
in to CS61's first problem set code and hit enter,
and you're wrong, well, your TF gets emailed,
and you lose minus one point.
Do it again, minus two points.
Do it again, minus three points.
So, trial and error, brute force not so smart.
So, what you'll find-- here's a hint
for your homework 12 months from now.
So, use GDB, because using GDB, as we've already seen,
can you poke around code?
Can you set break points?
And, in fact, that's how you can go about tackling
that particular problem set by dissecting the binary,
not just by running it and crossing your fingers
that you can guess what the professor's choice
of passwords are.
So, it's a really neat class to take after this, and you talk
about these kinds of low level details.
And those of you coming to this course with familiarity with
or experience in Java, these are really neat juicy details
that you just can't discuss in Java,
because in Java there are no pointers.
There are no direct memory addresses.
All of it is abstracted away, for better or for worse,
using things called references.
But the downside is that you don't have nearly
as much control of your machine.
The upside is adversaries don't have nearly as much control
over your machine, so you get something and lose something.
So with that said, let's pave the way for a little chat
about forensics, so not actually breaking machines,
but actually understanding how data is represented in recovery,
stuff we actually care about.
So, thus far in the course, we've pretty much talked
about chars, and strings, and ents, and floats, and doubles,
all of these primitive data types, but it's hard to imagine,
using just those primitives,
how you can implement anything more sophisticated,
like a Facebook website or a search engine,
which clearly needs to store more
than just individual numbers.
For instance, you might want to store
in some program you're writing a student, and a student
on campus is a real world entity,
and most students have an ID number.
They have a name.
And if they're undergraduates, they have a house.
So, it'd kind of be nice conceptually
if we could just kind of clump all of those fields together
and wrap them in a new data structure that we, ourselves,
can define, and that's where we can, again,
use this trick called type def for.
So type def, we saw once before
to declare what in CS50's library?
A string. So, we used a one-liner that said,
"Using type def, make 'string' a synonym for char*."
Well, using type def, can you define more interesting data
structures that aren't just synonyms?
They're brand new data structures that just don't exist
by default in C. The syntax for this is to say type def struct,
and then open brace and then enumerate with line by line,
typically, with semicolons at the end, each of the fields,
so to speak, that you want to put inside of a new data type
that you will henceforth call student.
I could call this anything I want,
but conceptually it seems sensible to call it student.
So if I now glance at the code,
of which you have a printout today, let me go ahead and go
into struct.h. This simply looks like this.
And let me quickly speak to this whole .h file.
So you guys have been using CS50.h, string.h,
standard lib.h, all of these header files.
The motivation for those files, again,
is so that you can tell the compiler, "Hey,
I want to use some functions that someone else wrote; and,
therefore, here's the file that declares all of those functions,
and maybe some constants, and maybe some other things."
But similarly, is it very common to use header files in C
to declare data structures that you, yourself, want to use,
and that other programs that use your code,
if you start writing more sophisticated programs
or libraries, themselves might want to use.
So in the interest of best practice, what I did,
even though this is a fairly simple program,
I factored out these new definitions,
this thing called a student.
I put it in its own file called structs.h, just by convention,
and what I then did in structs.c is what,
at the top of the file, presumably?
In structs1.c, I just do this.
So here's a slight difference in approach.
So there's a fundamental different approach between,
includes CS50.h, standard IO.h, standard lib.h, string.h,
and structs.h. Syntaxically, what's the obvious difference
between these five lines of code?
>> Quotes.
>> David: So, the quotes.
So instead of using angled brackets,
which means this is a default server library
or server header file that someone else preinstalled
on the server, you use double quotes around the file name just
to indicate this is a file that's
in the current directory that, presumably, I wrote.
So realize there is that distinction there.
The blue is a little hard to read here,
but apparently I'm using the sharp define preprocessor
directive to define a constant called student.
I didn't want to get bored by typing
in half a dozen students into this program.
I'm just going to type in three, but I could very quickly change
that by recompiling, after changing that constant.
And down here I have the following, a main function
that doesn't do all that much, but it does show us how
to use this new data structure.
So, again, you have a printout, if you'd like to follow along.
Notice what I've done at the top.
I want to declare a class of students.
So now, finally, consistent with this preaching
of using good style, declaring your variables with smart names,
well, let's start thinking about what we want to model,
just in colloquial terms.
I want to represent a classroom full of students, so I'm going
to call my variable class.
It's going to be of type student, but it's going
to be an array that has specifically three students
in it.
So this is just an array of three data structures
of type student; and, collectively,
I'm going to call that class.
Okay, so it's pretty easy now to refer to this.
So now I have a loop.
So for each of these students, I'm going to iterate from zero
up to students, which, again, is three.
Now notice the new syntax, if unfamiliar.
I'm first going to tell the user,
what's the first students ID.
Then I'm going to use the familiar, get ent, and I'm going
to use class bracket I.
So give me the Ith student in the class,
the Ith data structure, and then .ID.
This dot operator just says go inside this structure
and assign it to the field called ID.
So dot simply means go into the struct and access this field.
New syntax, not all that hard.
What's the student's name?
I do the same thing with string.
What's the student's house?
I do the same thing with string.
And then just to keep the formatting of my program nice,
I just print a new line after that.
So, now I've got a little curious.
I wanted to just use some other string functions,
and I decided somewhat arbitrarily I want to print
out any student who happens to be in Mather, a little biased.
So 4 ent I gets serial up to student,
so iterate over the whole class again, and here's a function
that should be familiar,
for those of you who've tackled Sudoku already.
If string compares, stir comp of the Ith student's house
"Mather" equals, equals zero--
well, we saw this briefly last week.
Stir comp returns zero if two strings are equal.
It returns a positive value
if one belongs before the other string, lexically, graphically,
or in a dictionary, or it returns less than zero
if it belongs after the word.
So, you have this ability to sort strings,
using this function as a building block.
I'm just using it for equality.
So, I'm checking, is the return value of stir comp,
given this string and given this other string,
equal, equal to zero?
If so, let me go ahead and print out who's in Mather?
What percent S is my placeholder?
Class, bracket I.name gives me the Ith student's name,
and it just happens to be a char*,
which is why percent S suffices.
And then finally, down here,
one of the most new important things that I've done.
Why do I now call free on every student's name
and every student's house?
>> To return memory.
>> David: Sorry?
>> To return memory.
>> David: So to return the memory,
but yet I didn't call malloc, right?
The rule of thumb last week, very simply,
was if you call malloc, you'd better call free at the end.
So, why am I, nonetheless, calling free here?
>> Because it raised our pointer.
>> David: Okay, because it raised our pointers,
raised our very much like pointers,
so that's the right direction, but I didn't call malloc.
Let's focus on that inconsistency.
Why am I calling free, even though I did not call malloc?
>> Get string.
>> So get string dict, right?
So one of the reasons for peeling back
that layer last week and looking briefly at the implementation
of get string is that all this time it's had this inherent
memory elite, because get string calls malloc to get as much ram
as is needed to store the string the user types in, but if you,
the person who's entrusted with that pointer,
after get string returns, does not free this, you can begin
to experience in your programs
that very familiar real world annoying feature
of some software that's poorly written
of your computer grinding to a halt eventually or having
to reboot, because everything is getting really, really slow,
even though you're not doing anything with the computer.
Quite often, is it simply a memory leak?
So, thereto is it important
to know what the functions are actually doing.
So, let's go ahead and compile structs 1.
I'm going to use make here.
I'm going to go ahead and run structs 1.
Student's ID, we'll call this student 11,
and this will be David, and David is in Mather.
Okay, student 12 will be Joe, and he'll be in Leverett.
And the student ID 13, this will be Sally.
She'll be in Foho [phonetic].
All right.
Hello, Sally.
So, David is in Mather.
Okay, so a very simple demonstration,
but nonetheless actually introduces finally this ability
to define our own date structures
and to even store those data structures inside
of other data structures like an array.
So, an array, even though it's barely a data structure,
it's just the same type of data type, back, to back, to back.
It's one of the first date types that we've actually looked at,
but this program is not terribly useful,
because I'm not doing anything with this information.
Once I hit enter, yes, it tells me who's in Mather,
but then it throws away all of that information.
In fact, the program very explicitly frees all
of that memory.
So, if I actually wanted to do something with this,
maybe I should use something like version 2 here.
So this, too, you have a printout of.
Notice that it's very similar to the code before.
I'm populating the class variable with the same data
as before, but before I quit this time,
I introduce a new loop that does this.
So, one thing we've not yet introduced,
and that will become invaluable when it becomes time
to actually recover JPEGs and other such things
for forensic purposes,
let's actually save these students to disc.
So a new function call here.
There's a function that exists in C and a whole bunch
of languages called F-open, file open.
Takes at least two arguments.
The first is the name of the file that you want to open.
Typically, if it doesn't exist, it will be created as a result
of this function call.
And then a second argument, which in this case, is "W".
Any guesses as to what the W denotes here?
W for write.
So this just means open the file, but open it in such a way
that I can write to it and change it,
not just read from it.
So that's useful, too, since, in this case,
we want data going out, not coming in.
Now FP not equal to null.
So, null, again, is this special value
that generally signifies errors.
Why, I might, just thinking intuitively,
why or when might F open return null, do you think?
Just a possible reason might it return null?
>> Another file with that name already
in the database folder with-- that's read only.
>> David: Okay, so maybe there's already a file called database
in my current directory, and maybe,
for whatever reasons, it's read only.
I, as the user, don't have the right to change that file,
because maybe it came with the operating system.
Maybe another user put it there.
I just don't have the privileges.
What's another reason that you might fail
to write a file to disc?
>> [inaudible]
>> David: Sorry?
>> No disc space.
>> David: No disc space.
Okay, so at some point, we might realize that as much as I want
to put these bits on disc, there's just not room,
so something has to fail at some point.
So let's take a look now.
I, at least, double check.
Is FD not equal to null?
Because if it's not null,
that means I've gotten back what's called a file pointer
or a file handle.
It's called any number of things, but it's just a variable
that somehow represent that file's location on disc.
Now I do this.
I go ahead and iterate three times from zero up to students.
And what do I do?
Well, I use this slightly different function that's very
similar to the one we've used.
Not print F, but F print F. What's really neat
about F print F is that it's the file version of print F,
and it just takes one additional argument that allows it
to distinguish itself from print F. The first argument here is
not the string you want to print, but a pointer to the file
that you want to print this sting to.
So this means send the following string to FP, that file pointer.
What string?
Percent dn.
What is the ent that should go there?
Just the student's ID.
After that, put the student's name.
After that, put the student's house.
And then, finally, after this loop is done, close the file.
So, what I've done is dump into a file student, after student,
after student, and each student's fields happen
to be on their own line.
So let me go ahead and compile this, make structs 2,
because the rest of the program is identical to structs 1.
Let me go ahead and run structs 2, enter, and now if I do this,
and then David, and then Mather, and then 13, and Joe,
and Leverett, and then 14, and then Sally, and Foho, enter.
Okay, so the program has behaved the same, but if I do an LS now,
notice I have this file that if I do an LS-L,
was just created a moment ago.
And as an aside, this is the size of a file.
This is when it was last modified.
LS-L shows you some interesting tidbits.
Let me go ahead and open database,
and voila, there's my database.
So what is my interpretation of a database here?
Just a text file that's got this data line,
after line, after line.
So, in effect, what I've kind of done now, albeit it very quick
and dirtily, I've come up with my own file format.
This is my, sort of David Malan's file format
for students.
I just have to know that a student record is stored
in three lines, one after the other, and I, myself,
just have to remember that the ID comes first, then the name,
then the house, then repeat some number of times.
So, now, if we take a step back and consider the real world,
when you've saved the file in Microsoft Word format,
or in HTML format, or in any file format that has one
of those three letter extensions, typically,
you are simply telling the program, save the contents
of whatever it is you want to save, in the proprietary format
at Microsoft, or Apple, or whomever it came up with.
Now, that just means that they decided, on their own,
how they want to put bits or how they want
to put characters on disc.
Probably, Microsoft Word is not as naive
as just storing the words in your file from top to bottom,
left to right, because there's a whole bunch
of junk in any Word document.
There's bold facing, italics, tabular information.
There's a huge amount of metadata,
so odds are Microsoft can't get away
with such a simple file format,
but some formats are relatively simple.
So JPEG photographs, when you take them with a digital camera,
actually are stored on disc, whether it's your hard drive
or your compact flash card, or your SD micro card,
whatever your technology is.
They're stored by storing a pattern of bits at the very top
of the disc that say here comes a JPEG.
Then there's some complicated mathematics that implement
that JPEG with a whole bunch of bits, megabytes worth of bits,
usually, and then sometimes at the bottom, there's a few bits
that say stop, this is the end of the JPEG.
And what you'll ultimately leverage in problem set five is
that signature at the top of the JPEG.
Just as here I could make this leap of faith and assume
that every there lines represents a student,
so in the context of forensics can you sometimes assume
that any time you see this pattern of bits,
aha, here comes a JPEG.
Let me just keep reading, reading, reading bits
until I see that pattern again,
at which point I know I've encountered what?
>> [inaudible]
>> David: Another JPEG.
So digital cameras, frankly, are pretty stupid when it comes
to storing information.
They generally write one photo, then the other right after it,
and the other right after it.
And so, in fact, you'll find
that using some basic building blocks
like these here today can recover
that data relatively easily.
Let me show you one other trick here, going back to a piece
of code we had last week.
We had this sample,
stupid program called Bar Dot C. You had a printout
of it last week, and it was really just meant
to demonstrate GDB, because it has a bunch of functions,
a bunch of variables, and I can step through each one.
Well, one of the most powerful features of GDB, especially now
that some of you are in experiencing seg faults
with increasing frequency, is to ask GDB, okay,
yes, I have a seg fault.
I know that, but where did it happen?
One of the things you can do with GDB is this.
I'm going to go ahead and run GDB on this program called Bar.
I'm going to set a break point at the function called bar,
because recall from this program that main calls foo
and foo calls bar, so I want to break,
once I'm pretty nested inside this program,
once I've got a bunch of frames on my stack.
So I'm going to go ahead and type run now.
It's broken right at the point where bar is executing.
Actually, let me get rid of that error message.
Make bar. Okay, so break in bar, run.
So it's going to break in the bar function.
So you can type list to see where you are in the program,
but what's really neat is you can type back trace or just BT
for short, and what this will show you, somewhat arcanely,
is a list of all of the frames you currently have
on your stack; in other words, all of the functions
that were called up until this point.
So, if you're running GDB, and you encounter a seg fault,
and you really don't know what went wrong, frankly,
you can just kind of infer where it happened
by typing back trace often.
You'll see all of the functions that may have been called.
Now, especially in Sudoku, where you're using
that fancy library called curses,
there might be not only your functions in there,
but a whole bunch of functions you didn't write.
Generally speaking, it's safe to assume
that those functions are correct.
So, much as you'd like to disagree,
odds are those functions, many of which have been
around for many, many years, are correct,
which means probably one of the functions you wrote,
that called that huge list of functions, is the culprit.
So, in this case, what I see here is this.
The oldest frame on my stack is this one here,
number two, for main.
After that, there's another frame on the stack for foo,
and then this third one for bar.
So what I can actually do here, BT for back trace again.
If I want to see, you know, what was going in main,
right now I'm in bar-- whoops.
Let me fix since I accidentally pasted something in.
Break bar, run.
Okay, so now this is bar.
Suppose that here's my back trace?
You can type frame, and then the number
of the frame you want to go to, frame two.
Now notice I'm in frame two.
It doesn't mean that I've said go continue executing main.
Go back to frame two and start executing.
This means let me poke around inside of this stack frame.
If we have this picture from last week
or even this fellow's here, when we have various frames
from the stack, this just means let me poke
around inside this frame, so that now I can type things
like print A, and I can actually see the value of A,
even though that variable is out of scope inside of bar.
And just to be kind of curious, notice what we can do here.
I'm going to rerun the program, so as to start from scratch.
So run is going to break at bar.
And let me do this.
Notice that bar has a local variable or really a parameter.
This is what bar looks like.
So I'm going to print M. All right, M, it was the value 10.
That's not interesting.
Let me print the address of M. So ampersand M is the address
of operator, so not I get a fairly looking hexadecimal
string, but that's just a fairly concise way,
we decided last week, of representing big numbers.
Hexadecimal, because you have more digits.
You can represent things more compactly.
And, yeah, look at this.
This is a pointer of type ent.
Okay, so this is a cryptic-looking address,
but let me now do this.
Let me go into the frame for main.
Main, itself, apparently has a variable A. I can do a sanity
check, print A. A was five, whatever,
but let's print the address of A, and now we have this value.
So now notice, even though this is a little cryptic,
this number is almost identical to this one.
This is from bar.
This is from main.
And now notice which of these numbers is bigger.
It's somewhat subtle, but which of these numbers is bigger?
They're almost the same.
Zero X, bravo, foxtrot, 976 Charley,
and then they only differ at two places, 60 and 9C.
Even if you're not quite comfortable
with hexadecimal yet, this one on the bottom is, in fact,
bigger, which confirms the prediction earlier
that when we are manipulating the stack,
these larger addresses are, in fact, down below.
Main, the address of Main's variable is bigger numerically,
its address, because it's lower in the stack.
It's one of the earlier stack frames.
So, here, too, using GDB, can we actually poke around with
such detail that we can see precisely the assumptions
that adversaries are exploiting.
So, that was a lot.
Let's take a five minute break.
All right, so we are back.
We are back, and so is lunch.
So not this Friday, but next Friday will be the next lunch
with CS50's team.
If you'd like to RSVP, just go to CS50.net/RSVP.
We will have to cap at ten,
just so we keep things sufficiently intimate,
so that we can actually talk with one another,
but check that out on the website, if you are available.
And free, so exit a small leap we've seen now multiple times.
It's going to recur, especially in the context of forensics
and our use of file IO.
Incidentally, file IO simply means input and output,
anytime you've seen that acronym somewhere.
And we've seen briefly here functions
like F-open and F-close.
We saw print F, the analog for reading is F scan F,
which we'll use before long.
F read and F write allows you to read and write,
not ASCII characters, but binary data, which is useful
when you're writing things that aren't, by nature, ASCII.
FEOF is just a function
that tells you am I at the end of file?
EOF. Yes or no.
So more on those in the time to come.
But before we get to this sexy picture,
a less sexy picture, hexadecimal.
So we saw this.
Zero, zero, zero, zero in binary represents what decimal number?
Easy question.
>> Zero.
>> David: All right, so zero.
But in hexadecimal, it also is represented as zero.
So hexadecimal digits conveniently can be represented,
hexadecimal digits conveniently represent four bits.
So, in other words, let's disregard decimal for today
and just say that this is hexadecimal
in the right-hand side.
If, instead, I want to represent the number one in binary,
but in hexadecimal this is simply one,
then if I fast forward to, say, 1111, this equals what in hex?
>> F.
>> David: So this equals F. So all ones, that is what?
The number-- let's see, this is the 8's column, plus 4's column.
That's 12, 13, 14, 15.
So 15 in decimal is F in hexadecimal.
All right, but we've been looking at numbers
that are much longer than just single characters, right?
We saw addresses like this thing here,
which clearly has multiple hexadecimal digits back-to-back.
So all this means is that you take the--
you take those numbers and then figure
out what the corresponding bit patterns are.
So, in other words, if I had this, one, two, three,
four zeroes in binary, followed by four ones in binary,
this would be represented in hex as zero F. Or just
to make clear the notation,
zero X just says here comes a hexadecimal value.
So zero F here.
If, instead, I did all ones-- one, two, three, four, five,
six, seven, eight-- and it doesn't line up,
because the zeroes are fatter-- that happens to represent what?
Well, this is the 128's column.
This is the 64's column.
This represents the value 255.
So the largest decimal number you can represent
with eight bits, we've seen long ago, is 255.
In hexadecimal, though, that's just zero XFF.
So, again, those of you who have some HTML background or play
around with Photoshop, you very often see precisely these
hexadecimal codes.
In fact, let me see.
This is somewhat tangential to CS50
but does demonstrate exactly where this stuff does come up.
So this is Photoshop, a very fancy photo manipulation tool.
This is the color wheel.
You'll notice that there's this mention
of RGB, red, green, blue.
So the way that numbers are represented--
and this actually will be useful for problem set five, as well,
as you'll see, they are represented as RGB triples,
a value for red, followed by a value for green,
followed by a value for blue.
And what this means is that pictures are made
up of pixels, little dots.
Every one of those dots has a color.
That color can be implemented with some amount of red,
some amount of green, and some amount of blue.
You can combine those in so many different ways
that you can essentially get every color of the rainbow,
just by using those values.
So, here, I have the value 00 00 00.
So that means no red, no green, no blue.
What do I get?
Well, the absence of all color here gives me black.
If, by contrast, I say give me a lot of red.
That's a lot of red.
So give me a lot of red, but now crank up the green,
then crank up the blue.
That gives me all of the colors.
And if you have all of the wavelengths
of light, you have white.
But as we just saw, this would be red.
If I want to see green, I would put the FF's
in the middle, because it's RGB.
And if I wanted to see blue, I have this on the end here.
So this just means you can string these hexadecimal
characters along and along
to form not four bit values but eight bit values.
So now, if I go back to GDB, if I want to try
to understand this a bit better,
this here is simply an eight bit value.
This here is simply an eight bit value.
Again, because every hex digit represents four bits,
which is one of the motivations for using hex at all is
because there is this really clean equivalence.
And then, finally, this here is also eight bits.
So, I have eight, plus eight, plus eight, plus eight.
So this just happens to represent a 32 bit integer,
which is really nice to see, because we said last week
that pointers are themselves 32 bit ents.
When you have a 32 bit machine,
that means its pointers are 32 bits.
And, voila, there is that ent represented, albeit in hex.
Now, if you find yourself looking more closely at some
of this buffer overflow stuff back at home on the slides,
you'll actually notice that some of these digits,
some of these hex digits are backwards on the diagram,
and it's not a mistake.
And that will actually come up in problem set five, as well,
a discussion of what's called little Indian-ness
and big Indian-ness.
Essentially, years ago, the world had to decide,
when we want to lay out multi byte numbers in memory,
do we go from left to right, or do we go from right to left?
It's a bit of an oversimplification.
P set five will tease this apart.
But, in short, different computers do it different ways.
And what you're seeing here is an artifact
of a decision made many years ago,
but the computer figures it out.
So CSI. So this is just kind of a silly way
of introducing the context
in which P set five will have you dabble.
So, years ago, a friend of mine literally had taken photos
on a digital camera, and something went wrong.
Like, his compact flash card or whatever it was got corrupted.
And at the time, I was very conveniently interning
as a graduate student for the local Middlesex District
Attorney's Office, where I was doing forensics work for them,
and it was really one of the best summer jobs, frankly,
I've ever had, because we were literally,
as I think I said weeks ago,
were taking in from the Mass State Police things
like hard drives, and CDs, and floppy discs,
and sometimes things that don't actually have data on them,
like monitors, and keyboards.
And so we just kind of piled that in a separate pile,
but we then had to answer questions
of the form, did he do it?
Right? Or is there any evidence to confirm
or deny this particular bad thing that happened?
And so much of this job was about going
through these hard drives and CDs, and, yes, as I've said,
just double clicking folders sometimes--
really not all that sophisticated,
some of the criminals in this county,
but sometimes people had, at least,
dragged things to the recycle bin.
Now, as most people in this room know, from experience,
or bad experience, dragging things to your recycle bin
or trash can doesn't really do anything
until you click what button?
>> Empty.
>> David: So empty trash or empty recycle bin.
So more on that in just a moment,
but there's even more worrisome aspects of data storage.
So, in fact, there was a really neat story a few months ago
about the iPhone.
Those of you with iPhones or iPod touches know
that when you push the button on the bottom there,
you actually get this fancy animation where everything kind
of shrinks down, and you then see your desktop.
Well, I believe the way Apple did,
or maybe still does implement that feature,
is they don't resize your whole window down to a little dot.
Rather, they very quickly take a screenshot
and then shrink hat screenshot,
because it's very easy to shrink an image.
It's a little harder to shrink actual applications.
Now the problem is a forensic analyst realized was
that people then, who might hit the home button,
while reading a really personal or really sketchy email
or IM had this paper trail on the flash memory
in their iPhones or iPods, because the moment they hit
that button, their phone or iPod took a screenshot.
That screenshot had to get saved somewhere on disc.
Now, these things don't use hard drives.
They happen to use flash memory, but it's the same idea.
Those zeros and ones got written
to the phone or the iPod's memory.
And if someone got curious or nosey enough
and had physical access to this phone, they could start reading
in all of those zeroes and ones.
And much like you will do for P set five,
they can just look for patterns.
And even if that screenshot was intentionally deleted
by the iPhone software, odds are it's still sticking around,
unless the user has hit that home button a whole bunch
of times or unless they've downloaded a whole bunch of MP3s
and movies since then that might probabilistically overwrite
those bits.
But there's yet other problems, too.
I mean, there's some very familiar ones.
If you've ever sat down at a computer and used a browser,
if you're visiting websites that you don't want anyone else
to know, you probably should do what
after stepping up from the computer?
Clear your cache or clear the history, right?
Or do any number of tasks,
but even those things are very imperfect.
And you've probably seen and maybe have kind of crossed
that ethical line of clicking your friend
or your roommate's history bar just to see explicitly
where they've been going.
[laughter] You laugh, because it's true.
[laughter] So it's because a lot of software, browsers being one
of the worst offenders, just remember a lot of information,
which tends to be useful for the user.
It means you can have auto completion, and it can remember
that you've been there, and it can cache.
So there's a lot of technically and UI useful aspects to this,
but all that data gets stored somewhere.
The history gets stored somewhere.
All of the JPEGs that comprise a web page that you visit have
to get stored somewhere.
And worse than that, computers these days have something called
virtual memory.
So long story short, most computers have,
these days, like what?
A gig of ram, two gigs of ram,
but the operating system actually lets itself think
that you have four gigs of ram or six gigs of ram,
because that's convenient.
And by having more ram, or more elusions of more ram,
can you then run more and more programs at once,
at least in the background, right?
You might not be interacting with all of them,
but if you tell, you trick your computer
into thinking this person has so much ram,
it means you can double click more icons
and have more stuff running at once, but the means
by which most computers implement
that elusion is they steal some hard disc space
or some flash memory space,
and they say pretend this space is ram.
And what the computer does, unbeknownst to you,
is when you start to run too many programs
that physically can't fit in ram, some of them get shuttled
to this thing called virtual memory.
They get copied from ram, which is purely electronic, to disc,
which is often mechanical, and it's slower,
but they do this transparently.
So you, the user, don't know where all of those bits are,
but you can sometimes infer where they are.
If you start to run more and more programs on your computer,
and you can simulate this tonight, what eventually happens
if you try running 10, 20, 30 programs at once?
Odds are they will open, but slowly.
The thing will slow to a crawl, and that's because a lot
of those programs, yes, they're getting loaded into memory,
but they don't fit in memory, so they go to virtual memory,
and just because of how this stuff is designed, hardware
and things like, mechanical things, like hard discs
and even flash memory are slower by nature and by cost
to then something like ram.
So you see this even in the real world.
Now, the takeaway here is that even if you cover your tracks,
and empty your recycle bin, and you clear your cookies,
and clear your history, and all of this, there is a good chunk
of hard disc space on your computer technically called swap
space-- many operating systems do this--
that still has a copy of all of that stuff.
So, in fact, one of the neat things
that Mac OS actually has--
I don't believe this has come built-in to windows yet.
Maybe 7 is different.
You have this little security tab here,
and there's this thing called FileVault.
So one of the things FileVault does is it encrypts your whole
hard drive so that even if you are doing sketchy things
or just private things on your computer,
all of that is encrypted using something a little more
sophisticated than Caesar Cipher, but the same exact idea.
And I actually don't remember-- oh, here it is.
So if I actually log in here, you'll see this.
There's this little icon, for those of you--
so this benefits half of you.
The other half, good luck.
But half of you can open up your security control panel
and check this.
Use secure virtual memory,
which means that feature I just described of swap space,
aka virtual memory, you can tell the computer,
albeit at a slow performance hit, to encrypt that, as well,
so that so long as I log off of this machine,
if someone steals it, and runs away,
and performs various forensic analyses on it,
there would be very low probability can they figure
out what bits were actually there.
So cryptography is really, really your friend these days.
And if you are liking this kind of stuff,
do bear in mind computer science 120,
which is offered in alternating terms.
So what's the implication here?
So let's consider a very simple example
of just storing some files on disc.
So inside of a typical computer is this thing called a
hard drive.
If it's still mechanical, which it is in most of your laptops,
unless you paid a bit of a premium to get SSD
or solid state drives, which is flash memory,
which has no moving parts, but the story is the same.
Inside of your computer is a hard disc,
and a hard disc is typically made up of these platters.
So if you recall floppy discs from many years ago,
there's those little circular floppy things,
hard drives have the exact same idea, but they're much thicker,
they're much stronger, and they spin a lot faster,
so they're more robust and store more bits.
But when you save a file to disc-- say it is a JPEG--
so a JPEG is going to be some kind of image that has kilobytes
or megabytes worth of data.
So supposed it takes up this many bits.
Now, I have no idea, as the user, where that JPEG ends
up on disc, so to speak.
The operating system decides for itself
where does it currently have space,
but it ends up somewhere there on disc.
What the operating system then does is it has a little table
called a directory table or something like that,
and it's essentially like an Excel spreadsheet
with at least two columns.
There's definitely more juicy stuff there,
and then there's one column called name,
and then another column called vocation or something like that.
And then the name of this file might be foo.jpeg.
Apologies for the handwriting.
And then location is a number.
We'll write it in hex, but it's just a number, 0X123.
And what that tells the operating system,
or reminds the operating system,
is the next time the user double clicks or searches
for foo.jpeg, go to what address?
Will go to this location on disc,
0X123 or whatever it happens to be.
Now what if the user decides, you know what,
this is a really private JPEG,
or this is just a really bad photograph,
let me just delete it.
And here she drags it to the recycle bin or trash can.
What happens to this picture?
So absolutely nothing.
So, first of all, most of you knew this.
If you drag something to the recycle bin or trash can,
unless you wait a few days, a month,
however long it is your OS keeps things around, nothing happens.
It's like dragging it to a separate folder.
But if you do have a little bit of savvy, and you do right click
and choose empty trash or empty recycle bin,
or wherever your menu option is, what then happens
to this picture, when you actually delete that file?
>> [inaudible]
>> David: Yeah, so this goes away.
Essentially, this goes away.
This goes away.
The operating system just forgets where that file is.
But for historical reasons and for performance reasons,
historically, this piece of the picture doesn't change, right?
Back in the day, computers were very slow, and the idea
of wasting time and making the user wait
so that you can then delete these bits, as well, well,
what would that even mean?
You can't just delete bits and erase them, right?
You need those bits; otherwise, your hard drive is going
to get perpetually smaller
and smaller every time you delete a file.
So, what would it mean, really, to delete a file?
Well, maybe change these zeroes and ones to all ones,
or all zeroes, or just random zeroes and ones.
But that used to take awhile.
So, to this day, most operating systems forget
where the file is, which is why programs like Norton Utilities,
if you're familiar, any of these tools that you might have
on your own computer, that lets you undelete files,
they generally just remember what this table used to look
like and then, with some probability,
can they go to the hard drive and get back those bits.
But I say, with some probability,
because what's probably going to happen, over time,
after you've deleted a file in this way?
>> [inaudible]
>> David: Yeah, so they're going to get reused.
The operating system eventually is going to say, you know what,
I need maybe not exactly those bits,
but I've got a pretty big JPEG that this user just downloaded,
and now I need these bits.
So, you know, in fact, and we used to see this
at the DA's office, we would see partial JPEGs.
We would lose part of the image, part of the gif,
whatever it was, but not necessarily all of it,
and that's just because, by chance, probabilistically,
some of those bits were reused elsewhere.
So you'll see in problem set five is what?
Problem set five is sort of like the end all of problems sets,
it seems, but it's really neat,
because it's really this intersection
of some very familiar technologies,
and we'll hand you this article written by a colleague of mine
from MIT, from grad school,
who did a really neat project himself, as a Ph.D. student.
He went on eBay with a bit of cash and started buying
up all these hard drives that people were selling,
100 gig drive here, a 500 gig drive here.
Then he imaged all of these drives,
much like Homeland Security
or the district attorney's office would,
and then he started analyzing all of these files,
all of these hard drives.
And what he found, as you might expect,
because these things get mentioned in the media once
in awhile, were people's social security numbers,
people's credit card numbers, pornography.
Anything that someone might have
on their hard drive ultimately made its way
to Maxwell Dorkin [phonetic] across the street.
But what was really neat-- so the point for him was not
to get some cheap pornography on eBay, but, rather,
to actually assess with what frequency this is happening
and what tools could we, could they, those users,
start using to more effectively, you know,
scrub their information.
And what the scary thing is--
and we'll present you with this paper in PDF form,
this article-- so many of the tools out there,
that you would pay good money for to, you know,
make sure that your financial documents are safe,
your personal documents are safe, so many of them are buggy.
And one aspect of this article was to find innumerable faults
with all of these tools that would overlook things
like the swap space, when wiping your hard drive,
or they would overlook something called slack space,
which this article will discuss.
But this, again, is one of the points of a course like this,
because by understanding, from the ground up,
how all of these little things work, one,
this kind of literature is accessible to you; and, two,
you understand what this machine is you guys use every day.
So with that said, we'll see you Wednesday.