Lecture Notes for Advanced Programming II

16 October 2001 - A Cautionary Tale

Fixed Arrays and Variable Data

• Fixed-sized arrays and variable-sized data are a bad combination.

  #define MAX_NO_KIDS 200
  
  printResults(LList & list)
  
    NodeDesc Nodes[MAX_NO_KIDS][MAX_NO_KIDS];
  
    buildTree(list, Nodes, numNodsPerLevel);
  
  
  buildTree(LList & list, NodeDesc Nodes[][])
  
    if (!list.findNode(Nodes[0][0], "root"))
      cout << "Didn't find root." << endl;
  
    list.getNextLevel(Nodes[0], Nodes[1]);
  
  
  getNextLevel(NodeDesc Node[], int size, NodeDesc kids[])
  
    int listIndx = 0;
    ListNode * currentPtr = firstPtr;
  
    while (currentPtr != NULL) {
      for (int i = 0; i < size; i ++)
        if (currentPtr->data.parent == Node[i].label)
          kids[listIndx++] = currentPtr->data;
        currentPtr = currentPtr->nextPtr;
  

• A matrix of nodes, one level per row.

Buffer Overflow

• This code has a buffer-overflow error.

  Progress Database Multiple Buffer Overflow Vulnerability
  www.securityfocus.com, 5 October 2001

  A problem in the software package could allow
  Progress is a commercial database[...].

  [...] exploitable buffer overflows are prevalent
  throughout many Progress Database programs [...]
  due to insufficient bounds checking [...].

  These problems could be exploited to [...] execute
  arbitrary code on a host with the privileges of each
  individual affected program.

  This situation could be leveraged by the attacker to
  gain root privileges on the host.

• A 40,000+ node tree will crash (or exploit) this code.

• But, at a cost.

  20:11:15 s0xxxxxx/submit
  22:46:21 s0xxxxxx/submit
  23:27:01 s0xxxxxx/submit
  02:54:51 s0xxxxxx/submit
  08:57:54 s0xxxxxx/submit
  11:49:42 s0xxxxxx/submit
  12:57:09 s0xxxxxx/submit
  14:43:24 s0xxxxxx/submit
  

Is There a Better Way?

• How can we crash the program with fewer nodes?

  • How are matrices laid out in storage? Row by row.

  • How is the matrix used? One level per row.

• A tree with 300 levels should do the trick.

• Success!

  • It works.

    300-level tree test
    
    ../../test-code[264]: 7879 Segmentation Fault(coredump)
    

  • It's fast.

    15:32:45 s0xxxxxx/submit
    15:33:06 s0xxxxxx/submit
    15:33:21 s0xxxxxx/submit
    15:33:29 s0xxxxxx/submit
    15:33:39 s0xxxxxx/submit
    15:33:53 s0xxxxxx/submit
    15:34:01 s0xxxxxx/submit
    15:34:13 s0xxxxxx/submit
    15:34:21 s0xxxxxx/submit
    15:34:30 s0xxxxxx/submit
    15:34:39 s0xxxxxx/submit
    15:35:57 s0xxxxxx/submit
    15:36:17 s0xxxxxx/submit
    15:36:25 s0xxxxxx/submit
    15:36:38 s0xxxxxx/submit
    15:36:47 s0xxxxxx/submit
    15:36:56 s0xxxxxx/submit
    15:37:03 s0xxxxxx/submit
    15:37:27 s0xxxxxx/submit
    15:37:33 s0xxxxxx/submit
    15:37:39 s0xxxxxx/submit
    15:37:48 s0xxxxxx/submit
    15:37:50 s0xxxxxx/submit
    

Avoiding Fixed Array Problems

• Check array indices.

  if (currentPtr->data.parent == Node[i].label)
    if (listIndex >= MAX_NO_KIDS)
      // die with an error message
    else
      kids[listIndx++] = currentPtr->data;
  

  • Unfriendly and inflexible, but safe.

  • This is always necessary.

• Dynamically allocate the matrix.

  // Warning - funky, incorrect syntax follows.
  
  NodeDesc ** tree = new NodeDesc[Llist.size()][Llist.size()];
  

  • A garguantian waste of space, bur flexible.

  • Not easy to do correctly.

• Use a dynamic data structure.

  typedef vector<vector<node> > Tree;
  

  • Little work required, flexible, reasonably space efficient.

  • Clumsy to use, not all that space efficient.

• Write your own custom data structure.

  • Efficient and effective use of time and space.

  • Looks like more work, but it isn't.

Lessons to Learn

• Don't write code with buffer overflows.

  • You're not going to pass this course.

• Variable-sized data and fixed-length arrays are trouble.

  • Disastrous if wrong, difficult and inflexible if correct.

• Good programmers control time as well as space.

  • 45 minutes vs. six hours.

• Make sure you really understand the problem before you solve it.

  • 40,000+ nodes vs. 300 nodes.

This page last modified on 6 December 2001.