« January 2004 | Main | March 2004 »

February 26, 2004

[Paper reviews] Formalizing C in HOL

[C formalised in HOL (ResearchIndex)]

Posted by jones at 10:40 AM | Comments (0)

February 22, 2004

[patents] Method ... for delivering zinc to the nasal membrane

[United States Patent: 6,080,783] Its an interesting sensation to have this gel thing in one's nose. It seems to take the edge off my colds though.

Posted by jones at 10:43 PM | Comments (0)

[patents] Cloth book with rigid support

[United States Patent: 6,131,952] The support thing works, but if you aren't sitting a table it tends to just get in the way. The twins love to play with it at church.

Posted by jones at 12:35 PM | Comments (0)

February 21, 2004

[Paper reviews] "Orthogonal defect classification..." by Chillaredge et al

["Orthogonal Defect Classification -- A Concept for In-Process Measurements,"] the link requires authentication with IEEE explore. May not work for everyone...

Full reference is: Chillarege, R., Bhandari, I., Chaar, J., Halliday, M., Moebus, D., Ray, B., and Wong, M. "Orthogonal Defect Classification -- A Concept for In-Process Measurements," IEEE TSE, vol. 18, no. 11 (Nov. 1992), pp. 943-956.

We like the classification scheme. I am particularly interested in which kinds of errors we think we will find with our tool. Then we can say more precisely how our tool will effect reliability using the seeded errors model. The error types are:


They claim that timing/serialization errors will appear late in the design cycle. That's good because that's where we are aimed and errors found late are more expensive to fix. We'll spit into timing errors, serialization errors, algorithm errors and assignment errors. We don't do much with the rest.

Posted by jones at 11:29 PM | Comments (0)

[Paper reviews] "Using testbeds to accelerate technology maturity... SCRover" by Boehm et al

[Using testbeds to accelerate technology maturity... SCRover" by Boehn et al] Interesting ideas about how to measure reliability and how to show that you've improved reliability using seeded errors. the results are in the context of UML architecture level work, but the ideas are interesting for us at the machien level.

Their seeded defect model for evaluating a technology's impact on reliability is particularly interesting. Here's some quotes:


Suppose an experiment shows that in a given situation, the technology being evaluated finds 3 defects. How can we tell whether this is 100% of 3 defects or 3% of 100 defects? The best technique found to date is the seeded defect technique adapted from previous statistical techniques to software testing [18].

[18] is H. Mills, "On The Statistical Validation of Computer Programs", IBM Federal Systems Division Report 72-6015, 1972.

If we insert 10 representative defects into the software, and the technology being evaluated finds 6 of them, the maximum likelihood estimate is that the technology has found 60% of both the seeded and the unseeded defects. In general, if we insert I seeded defects, and the technology finds S seeded defects and U unseeded defects the maximum likelihood estimate of the total number T of unseeded defects is T = I*(U/S).

The "seeded defects" are really just the defects found during normal code and architecture reviews. The experiment, then, is to see how many of those known, I mean seeded, errors were found using the new analysis technique.

"These defects were classified under a categorization schema similar to Orthogonal Defect Classification [5]" [5] is [5] R.Chillarege, I.S.Bhandari, J.K.Chaar, M.J.Halliday, D.S.Moebus, B.K.Ray, and M-Y.Wong, “Orthogonal Defect Classification- A Concept for In-Process Measurements”, IEEE Transactions on Software Engineering, 18(11), 1992.

The other interesting thing about the paper is their analysis of their Mae tool.


USC’s Mae technology serves as an intermediate step between the UML diagrams and the implemented system. Mae is an extensible architectural evolution environment developed on top of xADL 2.0 [6] that provides functionality for capturing, evolving, and analyzing functional architectural specification [21].

Basically, they are using UML to describe their system and they want to convince themselves that the UML diagrams say the right things. That's hard because UML isn't executable and doesn't have a formal model.

So their results are interesting, but not that applicable to our tool since we are working on machine code, not architectural level stuff.

In the end, I think we use the same seeded error model and work to improve the maximum liklihood estimate by finding more errors in the code until we are able to find all the errors in a piece of code. We focus in on the "most difficult, intracate 1000 lines of machine code in the software" Then throw the rest into the environment. Real time works because we have real time in the environment. That's not bad. year to year we show that we are decreasing the MLE for the number of remaining errors.

Open questions for us:


  1. What kinds of errors are we going to find? Look up the orthogonal error model.
  2. How are we going to seed errors? We are claiming that we can find errors that are difficult to fidn using any other method. So we have to have a method for seeding realistic errors without the ability to detect them.

Posted by jones at 10:36 PM | Comments (0)

[Research] NASA testbed details

[ NASA High Dependability Computing Program ] This is what we've been looking for. We need to read and digest this for the proposal.

Posted by jones at 08:53 PM | Comments (0)

[Research] 6811 code for a robot

[A Simple Robot Using the 68HC11 Processor] has a couple sensors, some motors, a time-based interrupt. Has behavior that depends on time. Just need to think of a way to make it need a mutex.

line following robot. Here's an interesting verification problem: Using a model checker, verify all line-following behaviors of a robot for all interrupt interleavings, input spaces and delay loop lengths. Consider the following:


The algorithm for the light-seeking behavior is quite simple. I read the values from the two voltage-divider photoresistor circuits with inputs 0 and 1 of the HC11's A/D converter. Whichever value is the largest (left or right), I turn the robot in that direction. Like the line-following code, I use arc turns rather than pivots to always provide forward movement. The program is a continual loop looking at the sensors and either arcing left or right towards the light.

Well, we did slightly modify this simple program (Figure 10). Since the HC11 can scan the A/D converters every 64µS, or over 15,000 times a second, the result was very jerky. The first modification was to delay for about half a second each time through the loop. This resulted in the robot going in slow arcs--still not what we were looking for. What we settled on was an arced turn for about a quarter of a second, then forward movement for another quarter of a second. This is the behavior implemented in the program.


I thought this was interesting too:

Adjustments in the software timing will be needed to work with different sized wheels.

Interesting reading from the motorola 68hc11 reference manual:

Posted by jones at 01:49 PM | Comments (0)

February 19, 2004

[Research] 68HC11 Instruction reference

[68HC11 Instructions] Includes cyle timing information.

Posted by jones at 09:10 AM | Comments (0)

[Research] GNU tools for 68HC11

[Using the GNU Development Tools for 68HC11 and 68HC12: Hello World Example] This is probably at better processor platform for our work.

Posted by jones at 08:30 AM | Comments (0)

February 15, 2004

[patents] Solution for pork products

[United States Patent: 5,989,610] well, it must have worked, since i picked my sundary dinner pork based on its shelf appearance.

Posted by jones at 04:35 PM | Comments (0)

February 14, 2004

[patents] Tool for scarifying wallpaper

[United States Patent: 5,074,045] Works pretty good for the vinyl paper backed paper we have in our room. The wallpaper is vintage 1985 green and pink sort of. The paper has served its purpose and its time to move on.

Posted by jones at 03:43 PM | Comments (0)

[Education] Do you know what you think you know?

[Unskilled and Unaware of It: How Difficulties in Recognizing One's Own Incompetence Lead to Inflated Self-Assessments] A student in my 312 class, Ben Coverston, who teaches at Northface University, pointed this article out to me. Its an interesting concept to think about in the context of teaching. I've been struggling to figure out how to close the feedback loop on my students' learning so they can accurately guage how much they know about the topic. This article suggests that this is not a bad idea, especially in light of our first exam results (which were not good).

Posted by jones at 03:01 PM | Comments (0)

February 13, 2004

[Tech Support] virtual desktops for Mac OS X

[CodeTek Studios, Inc.--Virtual Desktop 3.0 pro] It does desktops, hotkey switching and focus-follows-mouse. I've been using focus follows mouse religiously since I got my mac, even though its not supported.

Posted by jones at 04:04 PM | Comments (0)

February 09, 2004

[patents] Ornamental paper trimmer (D379193)

[United States Patent: D379,193] For use scrapbooking. The cutter eventually wore out its little groove and it doens't crop in straight lines any more. Perhaps less effort on the ornamental design and more design on the functionality would have been a good idea?

Posted by jones at 09:11 PM | Comments (0)

[patents] baby feeder (5,364,348)

[United States Patent: 5,364,348] I don't think I realize just how many patented items I use from day to day. So I've started to look up all the patents I find in a normal day. The first is for our twins. They love it.

Posted by jones at 09:04 PM | Comments (0)