Kerberos Blog

Most C programmers are familiar with buffer overflows, and know how to avoid them: delegate.  In krb5, for instance, our coding practices recommend using asprintf() for simple string concatenation, and the k5buf module for more complicated constructions.  If you delegate your string construction this way, you know you can’t overflow an output buffer unless you screw up really badly.

Integer overflows are comparatively shrouded in mystery.  Programmers may be vaguely aware that adding large numbers will produce something other than the sum of the operands, but don’t really know what to watch out for or how to avoid attacks.  You can’t delegate your integer operations without rendering your code unreadable (and slow).  The web is surprisingly unhelpful.  So, here’s what I’ve learned about reducing the risk of integer overflow attacks:

• Every time you write code which parses a number out of a string, or otherwise gets it from another trust domain, imagine that you’re getting the largest number possible.
• Subtract, don’t add.  If you find yourself writing “if (current + len > available)”, instead write “if (len > available - current)”.  If your code doesn’t allow current to grow larger than available, the subtraction will always yield a positive value and you can’t have overflow problems.  (However, you do still have to protect against the possibility of len being negative, if it’s a signed type and you constructed it naively.)
• Use unsigned types for lengths when appropriate.  (But avoid comparing signed and unsigned types; the semantics of such comparisons are more complicated than you’d expect.)
• If you do find yourself having to add unbounded values, you can generally test for overflow by checking if (a + b < a), assuming a and b are of the same unsigned type.  If you’re adding three values in one operation, or multiplying values, that technique doesn’t work.

Here are some thoughts about krb5’s regression test suite.  This is based mostly on my experience with krb5, Subversion, and other projects, and I’m sure these ideas could be greatly refined through research in the field.

For the most part, we have two different kinds of tests in the krb5 tree: unit tests and system tests.  The unit tests are typically in the form of C source files beginning with “t_”, which are compiled and (usually) executed when you run “make check”.  Sometimes the test program is self-contained, sometimes it produces output which is compared to an expected output file.  In a few cases, test programs are not executed (sometimes because they are merely tools to facilitate manual testing) or are executed but produce output which is not verified.

Partly because the framework for unit testing is so ad hoc, these unit tests are easy to write, and are popular among krb5 developers for that reason.  The primary challenges for unit testing in krb5 are isolation, coverage, and organization:

• By isolation, I mean the difficulty of testing components which talk to the network, to a database, or something else much more complicated than the component itself.  In the Java web programming world, it is common to use “inversion of control” to facilitate unit testing.  Instead of referring to lower-level modules directly, classes are constructed with references to the network object or the database object or whatever.  During unit testing, the classes can be constructed with dummy versions of those dependencies which are rigged to produce the desired results, or even to yield fake errors to exercise failure paths.  That’s a bit harder to do in C, unfortunately, so in krb5 a lot of code is bypassed in the unit tests and tested only by system tests.
• By coverage, I partly mean the amount of code not covered by unit tests, and partly mean the difficulty in measuring what is covered.  I made some progress on measuring coverage by bringing back partial support for static linking, which allows the use of gcov.
• By organization, I mean that the ad hoc nature of our unit tests make them inflexible.  There’s no easy way to run unit tests without system tests, or to run all the unit tests and produce a report of which succeeded and which failed (instead, “make check” simply aborts on the first unit test failure), and no way to identify a particular unit test.  I’m not sure how important this problem really is.

Unit testing is great where it exists, because it allows code to be improved with confidence.  It’s no fun to be staring at a grotty function using outdated infrastructure and idioms, and knowing that if you bring it up to date you might introduce some subtle bug because the code has no tests.

Whereas unit tests exercise small isolated pieces of code, system tests exercise complete programs.  Most of our system tests are implemented in tcl and run in the dejagnu framework.  expect and dejagnu do not receive a lot of love and are sometimes buggy on any given machine, and there aren’t very many developers who are excited to learn more about tcl in order to write more krb5 system tests.  When I think about replacement infrastructure for dejagnu, I think about the following challenges:

• Ease of setup and teardown: krb5 programs operate in an environment consisting of a KDC, a client, and (in many cases) a server, and in more complicated tests there may be multiple KDCs.  Test cases need to be able to construct environments to run programs in with minimal boilerplate.  This basically means that the testing infrastructure needs to be extensible with library functions like dejagnu is using tcl.
• Program interaction: expect automates the footwork of testing programs which interact with the user via the tty.  Either our replacement infrastructure needs to duplicate this functionality, or we need to structure our programs to avoid the need for tty interaction in test cases.  (That’s probably easier now that we are unbundling the rlogin/telnet/ftp applications and their system tests.)
• Output usefulness: our current dejagnu test suites output files named krb.log and dbg.log.  I have not been blown away by the accessibility of this information.  Hopefully any replacement infrastructure would be able to produce tidier and more useful debugging output.
• Debuggability of test failures: when a system test fails, what does a developer  have to do in order to execute the relevant code inside a debugger?  For our current dejagnu tests, the answer varies from slightly annoying for the tests/dejagnu tests (add “spawn_shell” to the test case, figure out the exact command being executed, and execute it by hand under gdb in the spawned shell) to downright aggravating for the kadmin tests (add a sentinel loop to the appropriate part of the test case, gdb attach to the tcl interpreter in which the test is being run via bindings, set a breakpoint, touch a file to deactivate the sentinel loop, and continue the interpreter).  Any replacement infrastructure should have a decent answer to this question.
• Performance: because of the amount of setup and teardown involved with each test case, system testing can be expensive.  In our case, because our software was originally designed to run on Vaxes, the actual setup and teardown costs are minimal, but the test suite can be slow because of sleep() statements peppered around the test suite, the delays from which are multiplied by multiple test passes.  We need to avoid these.
• Barriers to entry: any reasonable system testing infrastructure necessarily involves a lot of locally built infrastructure to handle all the problems mentioned above.  How hard will it be for developers to come up to speed on all this machinery in order to write new tests?  The answer depends mostly on the quality of internal documentation.

I don’t have ready solutions in mind to these challenges at this time.  Our preferred scripting language at this time appears to be Python, so future developments for the test suite infrastructure will probably lean in that direction.

Here’s a note about a little project I finished a few weeks ago.

We have three variables configuring what types of encryption can be used in krb5:  default_tgs_enctypes, default_tkt_enctypes, and permitted_enctypes.  In krb5 1.7 and prior, the syntax of these variables is just a list of enctype names.  That’s fine if you know exactly what you want, but not so helpful if you just want to add or remove some enctypes from the default list.  For example, if you want to disable DES and triple DES support, you could list all of the remaining enctypes, but then your krb5 installation wouldn’t support any future enctypes we add support for in later versions of krb5.

In krb5 1.7, we added the allow_weak_crypto variable, which globally disables enctypes we consider to be weak (chiefly single DES) if set to false.  That’s a step forward, but isn’t very flexible.

In krb5 1.8, you will be able to use a more flexible syntax for enctype configuration.  There are three additions:

1. The word DEFAULT expands to the default list of enctypes.
2. There are four defined “families” of enctypes based on the underlying cipher: des, des3, aes, and rc4.
3. You can put a ‘-’ before an enctype or family name to remove it from the list.

So if you want to disable a specific enctype like AES256, you could write “DEFAULT -aes256-cts”.  If you want to disable whole families, you can do so succinctly with something like “DEFAULT -des -des3″.  If you want to use only specific families of enctypse, you can also do that succinctly by naming the families, like “aes des3″.  If you want to prefer a specific enctype, you can move it to the front of the list by writing something like “aes128-cts DEFAULT”.

There is a fourth variable of importance to enctype configuration.  It is called “supported_enctypes”, and determines the default combination of key/salt-type pairs used when a principal is created or its password is changed.  Because of the added factor of salt types, the syntax of this variable is unchanged for krb5 1.8; you have to explicitly list all of the key/salt types you want to use.  We looked into eliminating the concept of “salt type” for krb5 1.8 so that this variable could work just like the other three, but there turn out to be a few complications.

krb5 1.8 is planned to be released around March 2010, plus or minus three months.

With any non-trivial software project, there are a variety of housekeeping tasks oriented around keeping development going and maintaining quality.  Housekeeping work needs to be kept in balance–too much focus on it and the project makes no progress; too little and the product becomes difficult to maintain and loses quality.  I signed onto the MIT Kerberos Consortium last October with the understanding that I would focus on these housekeeping issues, although I spend a fair amount of time on feature work.  Here are some of the areas I think about, without trying to draw too much focus away from user-visible improvements:

• Code style consistency: MIT Kerberos has been in development for decades, and historically there has not been a strong focus on consistency of formatting and idioms.  We have agreed on a set of rules for new work; the challenge now is converting our large body of existing code to follow these principles.  For this release cycle we have decided to do a “great reindent”–basically, to eliminate the use of tabs in our C sources and ensure that all code use four-space indents.  That’s only a small part of the style principles, but it’s one of the most noticeable parts.
• Function size: Ideally, most functions in MIT krb5 would fit within a screenful of text and be understandable at a glance.  Unfortunately, many of our functions have accreted over time to huge lengths, such as the 615-line krb5_get_init_creds().  It is hard to change functions like these with confidence since they are so complicated.  At some point, I would like to spend some time decomposing these monster functions into smaller parts.  Going forward, we can learn from this problem–when adding to the work a function performs, use a helper function rather than open-coding a complicated series of steps into an already moderate-sized function.
• Naming: At times, krb5 developers have been lazy about choosing intuitive names.  When a TGS request arrives at the KDC (i.e. when a client requests to acquire service tickets using its ticket-granting ticket), the KDC code invokes dispatch(), which invokes process_tgs_req(), which invokes kdc_process_tgs_req() and then does a whole lot of other stuff.  The latter two function names are essentially equivalent, making it unclear how labor should be divided between them.  A related problem is consistenct of abbreviations; for example, in the kadmin library, we have filenames like lib/kadm5/srv/svr_policy.c and lib/kadm5/srv/server_dict.c.  It is hard to even type one of these filenames when the word “server” has to be mentally translated into the keystrokes svr, srv, or server at different times. I would love to spend some time improving this situation at some point.  Going forward, we should pay attention to quality of naming when reviewing contributions and new work.
• Code documentation: the biggest problem here is that we don’t have krb5 API documentation.  We have plans to use doxygen for this but we haven’t yet done the work.  We also don’t have a culture of documenting our internal function contracts; you generally just have to look at the function name and arguments and guess what it’s supposed to do, or read the code to find out what it actually does.  Changing that in a code base of this size is a pretty massive undertaking, which I hope to make a dent in at some point.  For new code, we should insist on at least a brief comment before each function explaining its purpose.
• Regression testing: I could talk about testing for a long time, and I will do so in a later blog post.  The good news is that we have a fairly large test suite in krb5.  The bad news is that it isn’t comprehensive, much of it relies on technology which has fallen out of favor (dejagnu, and therefore tcl and expect), it isn’t always easy to add tests for new code, and it isn’t always easy to debug test failures.
• Portability testing: Thanks to Ken Raeburn, we have some infrastructure for regularly running regression tests on a variety of platforms.  Unfortunately, we have not been spending enough time debugging the resulting test failures.  Some of them are amusingly obscure–for instance, a recent one was that ftpd was sending replies to the client in the wrong order if the server-side user doesn’t have a valid home directory, as was true of one of the test accounts–but we aren’t taking advantage of the testing infrastructure if we aren’t getting to a clean baseline.
• Interoperability testing: We don’t do enough of this.  Events like the Interoperability Testing Workshop are a great opportunity to test new features against other implementations, but we should also be testing basic functionality against other implementations on a regular basis.  To accomplish this, we probably want to set up static infrastructure based on other implementations (such as a read-only Heimdal or Active Directory KDC) and create a separate suite of functional tests which invokes our code against that infrastructure.  We could also make more use of gssMonger.
• Static analysis: We make use of Coverity, a commercial product, to scan our code for potential defects.  It tends to find a lot of unimportant problems in old, well-tested code, but is pretty good at uncovering real problems in new code.  Unfortunately, I have had limited time to clean up the defects it finds in the current krb5 code base (although I have mostly purged libkrb5 of defects since I signed on).
• Build system: Like most open source C projects, we use autoconf for portability (but not automake or libtool) and make for the build itself.  I think autoconf is approaching the end of its useful life.  It’s good at ensuring portability to a lot of Unix systems few people care about, and bad about ensuring portability to Windows.  Autoconf tests are written in an obscure macro language (m4) on top of least-common-denominator Bourne shell; it’s rare to find a developer with the skill set to work with this, and rarer to find a developer who wants to.  Given infinite time, I would love to rework the krb5 build system using scons, which I think is the most promising successor to autotools and make.  (Update 8/25: After more reading, I think we would need to consider more carefully which cross-platform build tool to use, if we were to do this.)
• Version control: We use Subversion, which is an industry standing for open source projects and mostly does a fine job of maintaining our project history.  However, it’s not very good at merging or distributed development.  At some point it might be worth considering a transition to git, which has probably been gaining the most traction among DVCS tools in the open source world.  Currently Subversion hasn’t reached the pain point to make this transition a priority.
• Bug tracking: Lest I sound too negative about everything, I think we have a perfectly satisfying bug tracking infrastructure using RT.  I wish we could keep up with the tickets better, but that’s a universal constant in open source work and probably in software work in general.
• Release management: The accepted practice when I signed on was to have a major release (1.x) every 18 to 24 months, with a three-month testing period, and patch releases (1.x.y) as necessary.  Such a long release schedule makes it difficult to avoid the temptation to cram new features into the release during the testing period or in patch releases.  For the future, we have agreed to use a 6 to 12 month release schedule with a shorter testing period.
• Project management: We use a pretty informal project management discipline defined here.  We made some modifications to it recently to hold more of the discussion of projects on the mailing list and less on the wiki.  By and large I like how it works, and don’t plan to make any changes.

As you can tell, it would be easy to spend all of my time on these issues alone, and probably all of several other people’s time as well.  For better or for worse, we don’t have that luxury.  If you have opinions about how we should be prioritizing the time we spend on code quality or on approaches we should take, your comments are welcome.