So last week I posted on the difference between trusted and trustworthy code. Picking up that thread again, if there is some code in my system that is trusted how can I tell if it is actually trustworthy?
Now ruling out truly malicious code, our assessment of the trustworthiness of code, really comes down to an assessment of the quality of the code, and a pretty reasonable proxy for code quality is the number of errors in the code, or more specifically, the lack thereof. So the question is how can we determine whether a piece of code has a small number of bugs?
The number of errors in a body of code is going to be the product
of two important factors: the defect density and the size of the
code. So, in general the defect density is measured in bugs per
thousand lines of code (KLOC), and the size of the code is measured in
lines of code. Now there are plenty of arguments on what the
”right“ method is for measuring lines of code, and in general
you can only know the exact defect density after all the bugs are found,
and of course, program testing can be used to show the presence of
bugs, but never to show their absence!
*. So, to lower the number of
bugs that exist in a code base there are really two options: reduce
the number of lines of code, or improve the defect density.
So, how do we improve, that is reduce, the defect density. Well, there are a number of pretty well known ways. Effective testing, despite its caveats, goes a long way to reducing the number of bugs in a code base (assuming that you actually fix the bugs you find!). Static analysis (in its various forms), is also an important tool to help increase the quality of code, and is often a great complement to testing as it can expose bugs in code that is impractical to test. And of course there are other formal methods like model checking which can help eliminate bugs from the design phase. A great example of this is the SPIN model checker. Code reviews, while time intensive, are also a great way of finding bugs that would otherwise fly under the radar. Another way to improve code quality is to write simple, rather than complex code. McCabe’s cyclomatic complexity measure can be one good indicator of this. There is, of course, just a sampling of some of the aspects of software quality. Wikipedia and McConnell’s Code Complete for more information.
Now, how do you know if some code base has actually undergone testing, how do you know if static analysis has been performed on the source code? How do you know if the code has under gone a thorough code review? Well, generally there are two ways, you trust the developer of that code, or you get someone you do trust to do the quality analysis (which may be yourself). Now, is the point where things quickly shift from technological solutions into the fuzzy world of economics, social science, psychology and legal theory as we try to determine the trustworthiness of another entity, be it person or corporation. The one technologically relevant part is that it is much more difficult to do a 3rd party analysis of code quality without access to the source code. Note: this I am not saying that open source software is more trustworthy, simply that making the source available enables 3rd party assessments of code quality, which may make it easier for some people to trust the code.
So, improving code quality, and thereby reducing defect density, is one side of the equation, but even if you have a very low defect density, for example, less than 1/KLOC, you can still have a large number of bugs if your code base is large. So it is very important to reduce the size of the code base as well. A small code base doesn’t just have the direct benefit of reducing the code size part of the equation, it also helps improve the defect density part of the equation. Why? Well, almost all the techniques mentioned above are more effective or tractable on a small code base. You can usually get much better code coverage, and even a reasonable amount of path coverage, with a smaller code base. Code reviews can be more comprehensive. Now to some extent those techniques can work for large code bases, just through more programmers at it, but using static analysis is another matter. Many of the algorithms and techniques involved with static analysis have polynomial, or even exponential computational complexity with n based on number of lines of code. So an analysis that may take an hour on a 10,000 line code base, could end up taking all week to run on a code base of 100,000 lines of code.
Of course, this doesn’t address the problem of how you assure that the code you think is in your TCB is really what you think it is. That topic really gets us into trusted boot, trusted protection module, code signing and so on, which I’m not going to try and address in this post.
Now, it should be very clear that if you want to be able to trust your trusted computing base, then it is going to need to be both small and high quality.
If you’ve seen me give a presentation recently, or just been talking about some of the stuff I’ve been doing recently, you’ve probably heard me mention the term trusted computing base or TCB. (Not to be confused with thread control blocks, the other TCB in operating systems). So what is the trusted computing base?
The TCB for a given system is all the components, both hardware and software, that we must be relied upon to operate correctly if the security of the system is to be maintained. In other words, an error that occurs in the TCB can affect the overall system security, while an error outside the TCB can not affect the overall system security.
Now, the TCB depends on the scope of the system and the defined security policy. For example, if we are talking about a UNIX operating system, and its applications, then the trusted computing base contains at least the operating system kernel, and probably any system daemons and setuid programs. As the kernel enforces the security mechanism of process boundaries, it should be obvious that an error in the kernel can affect the overall system security. Traditionally on UNIX, there is a user, root, who is all powerful, and can change the system security policies, so an error in any piece of software that runs with root privileges also forms part of the trusted computing base. Of course, any applications are outside the trusted computing base. An error in a database server should not affect the overall system security.
Of course, if we are using a UNIX operating system as the foundation of a database server, then the definition of the TCB changes. In this case not only is the operating system part of the TCB, but the database server is as well. This is because the database server is enforcing the security of which users can access which rows, tables and columns in the database, so an error in the database server can clearly impact the security of the system.
OK, so we now know we have to trust all the code that falls inside the TCB if we want to put any trust into our security system. The problem is, just because we have to trust this code does not give us any rational reason to believe that we can trust this code. Just because code is trusted doesn’t give us any indication at all as to whether the code is, in fact, trustworthy.
To put any faith in the security of the system we should ensure that any trusted code is trustworthy code.
There are a number of things that we can do to increase our confidence in the trustworthiness of our code, which I will explore in coming posts. For more information on the trusted computing base, the Wikipedia page gives a good overview, and links to some useful papers.
I recently spoke at the Open Mobile Exchange (OMX), at the O’Reilly Open Source Conference (OSCON). Now, a totally fantastic thing about OSCON, is that there is an easy way for audience members to provide feedback to speakers via the conference website. (Unfortunately, I was spending too much time prepping my slides to give useful feedback to my other speakers, which I must apologise for.) I really hope that the zookeepr guys add similar functionality so linux.conf.au can have similar feedback mechanism.
So, the great thing is that I got some great feedback from my last talk, which confirmed something I was worried about in my talks. When giving a talk, there is always a lot of background material that I feel I need to cover to adequately explain my position, but the problem is that I then have a lot less time to present the crux of my position.
So I’ve decided that I’m going to try and cover background information on my blog, so that I can refer to that in my talk, rather than going into lots of detail during the talk. This also gives all those people with laptops something useful to do during my talk.
Stay tuned!
On the 10th anniversary of the creation of Symbian Ltd, Nokia has announced that they will be acquiring Symbian Ltd with the aim of opening up the Symbian OS under an Eclipse based license. The mobile operating system market is really getting a shake up at the moment!
The Symbian Foundation has been created to build a new platform for mobile phones based on Symbian OS, S60, UIQ and MOAP(S). The foundation is expected to launch in H1 2009.
The new Symbian Foundation Platform will be made up of a common setup application suites, runtimes, UI framework, middleware, OS, tools and SDK, with Foundation members able to provide differentiated experiences on top. The platform is expected to be released to foundation members in 2009, and eventually open sourced over the following two years.
This obviously makes a huge change in the market place. It wll be interesting to see how Symbian Platform, vs. Android, vs. LiMo, vs. Windows Mobile vs. iPhone.
Of course it is all about developers, developers, developers, and it will be extremely interesting to see where developers will want to go.
I’ve, recently started using memoize.py,
as the core of my build system for a new project I’m working on. This
simplicity involved is pretty neat. Rather than manually needing to
work out the dependencies, (or having specialised tools for
determining the dependencies), with memoize.py, you
simply write the commands you need to build your project, and
memoize.py works out all the dependencies for you.
So, what’s the catch? Well, the way memoize.py works
is by using strace to
record all the system calls that a program makes during its
execution. By analyzing this list memoize.py can work out
all the files that are touched when a command is run, and then stores
this as a list of dependencies for that command. Then, the next time
you run the same command memoize.py first checks to see
if any of the dependencies have change (using either md5sum, or
timestamp), and only runs the command if any of the dependencies have
changed. So the catch of course is that this only runs on Linux (as
far as I know, you can’t get strace anywhere else, although that
doesn’t mean the same techniques couldn’t be used with a different
underlying system call tracing tool).
This technique is quite a radical difference to other tools which
determine a large dependency graph of the entire build, and then,
recursively work through this graph to fulfil unmet dependencies. As
a result this form is a lot more imperative, rather than declarative
style. Traditional tools (SCons, make, etc), provide a language which
allows you to essentially describe a dependency graph, and then the
order in which things are executed is really hidden inside the tool.
Using memoize.py is a lot different. You go through
defining the commands you want to run (in order!), and that is
basically it.
Some of the advantages of this approach are:
There are however some disadvantages:
ptrace to perform the system call tracing.memoize.py
a little so that you could simply choose not to run strace. Obviously
you can’t determine dependencies in this case, but you can at least build the
thing.As with may good tools in your programming kit, memoize.py is
available under a very liberal BSD style license, which is nice, because I’ve
been able to fix up some problems and add some extra functionality. In particular
I’ve added options to:
The patch and full file are available. These have of course been provided upstream, so with any luck, some or most of them will be merged upstream.
So, if you have a primarily Linux project, and want to try something
different to SCons, or make, I’d recommend considering memoize.py.
I recently posted my videos from linux.conf.au earlier this year. I ended up spending a lot of time in post-production with these, probably more than I spent in preparing for the talk (and coming up with all the demos for the talk was a lot of work too!).
I ending up shelling out for Final Cut Express (FCE) as I really couldn’t find anything in the free/open source arena that could really do all the effects that I wanted. My biggest shock was how bloody difficult it was to actually use! Don’t let the express part fool you, the learning curve is far from quick. I was also a bit surprised how film oriented FCE is. It is much more geared towards production of video captured on tape that will be viewed on a real screen, than towards digitally captured video destined for the web. (Or at least that was my impression).
The other surprising bit of the process was that I really couldn’t find a suitable place to host my video on the web. Most of the free video places didn’t want hour long movies, and I found the quality of the video once it was transcoded to be pretty terrible in most cases. This is probably due to the fine detail that I’m attempting to show, which probably doesn’t get treated too nicely by most encoders. In any case, I ended up hosting the video using Amazon web services, since the storage a transfer fees were a lot more attractive than slicehost (where the rest of my website is hosted).
Any way, as with most of my posts, the main point of this one was to remind future Benno how to export decent quality movies with FCE. (There are about a million different options to play with, and it took a lot of tweaking to get right). So, in summary, you want something along the lines of:
Format: QuickTime Movie
Options
-Video
-Settings
Compression Type: H.264
Motion:
Frame Rate: Current
Key Frames: Automatic
Frame Reording: x
Data Rate:
Data Rate: Automatic
Compressor:
Quality: Best
Encoding: Best
-Filter: None
-Size:
640x480
Preserve: using letterbox
Deinterlace
-Sound
Linear PCM
Stereo L R
Rate: 48khz
Render Settings: Quality: Normal Linear PCM Seetings: Sample Size: 16 Litte Endian: x
-Prepare for stream --- nope
To get Ogg Theora output, using the XiphQT tools.
One of the best/worst things about doing your own post production is that you become very familiar with your own annoying habits and tics. If you watch the video, um, I’m sure you will, um, realise, um, what I, um, mean. (Note to self: rehearse my talks more!)
By the end of the editing process I was both sick of my own voice,
and sick of anyone who says computers are fast enough
,
when you spending a good 14 hours encoding and compressing a video,
you realise that for some things, computers are still damn slow. I would
expect most encoding and compression is reasonably easily paralellisable
(if that is a real word?), so this massively multi-core revolution will
hopefully help my future video editing projects.
Earlier this year I presented at the linux.conf.au embedded miniconf, about how to port OKL4 to a new SoC. The video was taped and had until recently been available on the linux.conf.au 2008 website, but for some reason that website has gone awol, so I thought it was a good time to put up my own copy. These videos have the advantage that they have gone through a painstaking post-production phase, which seamlessly meld the slides into the video (well, not quite seamless), and also all the bad bits have been removed.
This presentation gives a really good overview of what is involved in porting OKL4 to a new SoC. However, please note that the specific APIs have been somewhat simplified for pedagogical reasons, so this is more an introduction to the concepts, rather than a tutorial as such.
The videos are available in Ogg/Theora and also Quicktime/H264 formats, and either CIF (352x288) or PAL (720x576). If you can afford the bandwidth I would recommend hi-res ones, as then you can actually see what is one the screen.
You know that any blog post with musings in the title is going to be a lot of navel-gazing babble, so I don’t blame you if you skip out now, this is mostly for me to consolidate my thoughts on literate programming.
The idea behind literate programming that you should write programs with a human reader as the primary audience, and a compiler as the secondary audience. So this means that you organise your program in logical orders that aid explanation of the program; think chapters and sections, rather than organising your program in a way that is oriented towards the compilers; think files and functions.
Some of the outcomes of writing your programs in this literate manner is that you think a lot more about how to explain things to another programmer (who is your audience), than if you are writing with the compiler as your audience. I’m quite interested in things that can improve the quality of my code personally, and of my team’s code. So I thought I’d try it out.
I first tried a somewhat traditional tool, called noweb. I took a fairly complex module of a kernel that I’m writing as the base for this. The output that I produced from this was some quite nice look LaTeX, that I think did a good job of explaining the code, as well as some of the design decisions that might have otherwise been difficult to communicate to another programmer. I was able to structure my prose in a way that I thought was quite logical for presentation of the ideas, but ended up being quite different to the actual structure of the original code. It is no surprise that the tool to take the source file, and generate source files to be used by the compile is called tangle. Unfortunately I can’t really share the output of this experiment as the code is closed (at the moment).
While I liked the experience of using noweb, it seem a lot like a case of write the code, then write the documentation, and then going back to modify the code would be a real nightmare. There is a lot of evidence (i.e: working bodies of code) that a body of code can be worked on by multiple people at once reasonably effectively. I’m yet to see a piece of literature that can be effectively modified by multiple parties. (And no, Wikipedia doesn’t count).
One person who agrees is Zed Shaw. He agreed so much that he made his own tool, Idiopidae that allowed you to have code, but then separately create documentation describing that code, in a mostly literate manner, in a separate file. This seemed like a good altnernative, and I tried it out when documenting simplefilemon. Here the documentation is separate, but the code has markers in it so that the documentation can effectively refer to blocks of code, which goes some way to eliminating the problems of traditional literate programming. For a start syntax hi-lighting actually worked! (Yes, emacs has a way of doing dual major modes, but none of them really worked particularly well). When doing this approach, I have to admit it felt less literate, which is pretty wishy-washy, but I felt more like I was documenting the code, rather than really taking a holistic approach to explaining the program. Of course, that isn’t exactly a good explanation, but it definitely felt different to the other approach. Maybe I felt dirty because I wasn’t following the Knuth religion to the letter. I think this approach probably has more legs, but I did end up with a lot of syntactic garbage in the source file, which made it more difficult to read than it should have been. Also I couldn’t find a good way of summarising large chunks of code. So for example, I could present code for a loop with the body replaced by a reference to another block of code, which is one of the nice things I could do in noweb. Of course that is probably something that can be added to the tool in the future, and isn’t really the end of the world.
Where to go next? Well, I think I’m going to try and go back and reproduce my original kernel documentation using Idiopidae to see what the experience is when only modifying one variable (the tool), and see how that goes. If that can produce something looking reasonably good, I think I might invest some time in extending Idiopidae to get it working exactly how I want it to.
While I end up using Mac OS X as my primary GUI, I still do a lot of development work on Linux. I'm using VMware Fusion to host a virtual headless Linux machine, which is all good. Recently I decided to upgrade my OS to Ubuntu 8.04, which promotes have a just-enough OS (jeOS), which seemed perfect for what I wanted to do. Unfortunately the process of getting the VMware client tools installed was less than simple. Cut a long story short, the fix is described by Peter Coooper, and things work well after that. (It is a little annoying that the Ubuntu documentation doesn't explain this, or link to this.).
Anyway, after this I'm able to share my home directory directly between OS X, and my virtual machine, which is absolutely fantastic, as I'm not using TRAMP or some network filesystem to shuffle files back and forth between the virtual machine and the main machine.
Unfortunately, I ran into a bit of a problem, specifically, history
was not working in zsh. Specifically
saving the history into the history file was not working, which is a
really painful situation. It was not really clear why that was, running
fc -W manually didn't work either, but managed to fail
silently, no stderr output, and no error code returned.
Failing this I went back to the massively useful debugging tool
strace.
This finally gave me the clue that link() (hard linking) was
failing. I confirmed that using ln.
So, it turns out that the VMware hgfs file system doesn't support
hard linking, which is a real pain, especially since the underlying OS
X file system supports hard linking. So I'm down to the work around of storing
my history file in /tmp rather than my home directory, which
is slightly annoying, but not the end of the world.
As it turns out I'm not the first to discover this, Roger C. Clermont also found this out a few days ago. With any luck we will find a solution in the near future.
Mac OS X has the kevent()
system call which allows you to monitor various kernel events. This is kind of
useful, because I want to, well, watch a file, and then do something when it
changes. Now, I would have thought I could find something really simple to
do this, but I could only find massive GUI programs programs to do this, which
is not so great for scripting.
Anyway, long story short, I decided to write my own. It was pretty straight
forward. I thought it was worth documenting how it works so that Benno 5 years
from now can remember how to use kevent.
The first important thing you need to create a kernel queue using
the kqueue()
system call. This system call returns a descriptor which allows you
get to use on calls to kevent(). These descriptors come
out of the file descriptor namespace, but don't actually get inherited
on fork().
19 | int kq;
|
77 78 79 80 | kq = kqueue();
if (kq == -1) {
err(1, "kq!");
}
|
After creating the kernel queue, an event is register. The
EV_SET macro is used to initialise the struct
kevent. The 1st argument is the address of the event structure
to initialise it. The 2nd argument is the file descriptor we wish to
monitor. The 3rd argument is the type event we wish to monitor. In
this case we want to monitor the file underlying our file descriptor,
which is this EVFILT_VNODE event. The 5th argument is
some filter specific flags, in this case NOTE_WRITE,
which means we want to get an event when the file is modified. The
4th argument describes what action to perform when the event
happens. In particular we want the event added to the queue, so we use
EV_ADD & EV_CLEAR. The EV_ADD is obvious,
but EV_CLEAR less so. The NOTE_WRITE event
is triggered by the first write to the file after register, and
remains set. This means that you continue to receive the event
indefinitately. By using the EV_CLEAR flag, the state is
reset, so that an event is only delivered once for each
write. (Actually it could be less than once
per write, since events are coalesced.) The final arguments
are data values, which aren't used for our event.
The kevent system call actually registers the
event we initialised with EV_SET. The kevent
function takes a the kqueue descriptor as the 1st argument. The 2nd and
3rd arguments are a list of events to register (pointer and length). In this
case we register the event we just initialised. The 4th and 5th arguments
is a list of events to receive (in this case empty). The final argument
is a timeout, which is not relevent in this case (as we aren't
receiving any events).
59 | struct kevent ke;
|
83 84 85 86 87 88 89 90 91 92 93 94 | EV_SET(&ke,
/* the file we are monitoring */ fd,
/* we monitor vnode changes */ EVFILT_VNODE,
/* when the file is written add an event, and then clear the
condition so it doesn't re- fire */ EV_ADD | EV_CLEAR,
/* just care about writes to the file */ NOTE_WRITE,
/* don't care about value */ 0, NULL);
r = kevent(kq, /* register list */ &ke, 1, /* event list */ NULL, 0, /* timeout */ NULL);
if (r == -1) {
err(1, "kevent failed");
}
|
After we have registered our event we go into an infinite loop
receiving events. In this time we aren't setting up any events,
so it is the list to register is simply NULL. But,
4th and 5th argument have a list of up to 1 item to receive.
In this case we still don't want a timeout. We want to check
that the event we received was what expected, so we assert
it is true.
33 34 35 36 37 38 39 40 | r = kevent(kq,
/* register list */ NULL, 0,
/* event list */ &ke, 1,
/* timeout */ NULL);
if (r == -1) {
err(1, "kevent");
}
assert(ke.filter == EVFILT_VNODE && ke.fflags & NOTE_WRITE);
|
The aim of this program is to run a shell command whenever a file
changes. Simply getting the write is not good enough. A
progam that is updating a file will cause a number of consecutive
writes, and since it is likely that our shell command is
going to want to operate on a file that is a consistent state, we want
to try and ensure the file is at a quiescent point. UNIX doesn't
really provide a good way of doing this. Well, actually, there is a
bunch of file locking APIs, but I guess I haven't really used them
much, and it isn't clear if the file writing would be using them, and
as far as I can tell, the writing file would have had to be written
using the same locking mechanism. Also, the commands I want to run are
only going to be reading the file, not writing to it, so at worst I'm
going to end up with some broken output until the next write. Anyway,
to get something that will work almost all the time, I've implemented
a simply debouncing technique. It is a simple loop that waits until
the file is not written to for 0.5 seconds. 0.5 seconds is a good tradeoff
between latency and ensuring the file is quiescent. Of course it is
far from ideal, but it will do.
To implement this a struct timespec object is created
to pass as the timeout parameter to kevent.
21 | struct timespec debounce_timeout;
|
72 73 74 | /* Set debounce timeout to 0.5 seconds */
debounce_timeout.tv_sec = 0;
debounce_timeout.tv_nsec = 500000000;
|
In the debounce loop, kevent is used, but this time
passed with the 0.5 second timeout.
41 42 43 44 45 46 47 48 49 50 | /* debounce */
do {
r = kevent(kq,
/* register list */ NULL, 0,
/* event list */ &ke, 1,
/* timeout */ &debounce_timeout);
if (r == -1) {
err(1, "kevent");
}
} while (r != 0);
|
Finally after the debounce, we run the command that the user specified on the command line. The following code shows the declaration, initialisation and execution of the command.
20 | char *command;
|
70 | command = argv[2];
|
51 | system(command);
|
To use simplefilemon is easy. E.g: simplefilemon filename "command to run".
You can compile simplemon.c with gcc simplefilemon.c -o simplefilemon.
Download: simplefilemon.c