« August 2003 | Main | October 2003 »
September 30, 2003
[Misc.] things to change
move definition of factors to first use of factors.
re emph that goal is objective.
define metrics, params, workload, etc at first use.
analysis incldues statistical methods.
what is the difference between factors and parts of an algorithm?
Spending more time on writing the proposal than thinking about the experiment.
pitfall: We want people to think about their experiments in advance arther than running an experiment and realizing that thea its't wahat they wanted to run in the fist place.
pitfall: one week spent runing experiments can save you 2 days thinking about your experiments.
take out bugos numbers change to "axes on chart and table columns"
take the hope out of goals. Make it objective.
"and run the command" to "be able to run the command"
"one command" goes to "one command to submit and one command to collect"
Posted by jones at 09:29 AM | Comments (0)
September 29, 2003
[Misc.] Bug snax
[Larvets - The Original Worm Snax] in three "mouth-watering flavors: BBQ, Cheddar Cheese and Mexican Spice" Wow.
Posted by jones at 09:56 PM | Comments (0)
[Research] Java PathFinder source
[JPF Source Code Release] fill out forms, get them signed. etc.
Posted by jones at 09:38 AM | Comments (0)
September 27, 2003
[Tech Support] Visual Basic and Access Programming Run
[Splitting a string in VB, accessing records in an Access DB] The time has come to generate a Ward list from the MIS info in a reasonable format. Since the LDS Church is likely coming out with a new MIS in January, I could just do this by hand just this once and be done with it. But that wouldn't be as fun.
Posted by jones at 08:34 AM | Comments (0)
September 26, 2003
[Tech Support] Finding your MAC address in XP
from [How to identify you wireless card MAC address] Open a command prompt, type ipconfig /all, find the right entry and look for the "Physical address" entry in the form xx-xx-xx-xx-xx-xx.
Posted by jones at 09:54 AM | Comments (0)
[Paper reviews] Two Dependability Papers
Ideas for the design of a benchmark suite that measures the dependability of an operating system Measuring Software Dependability by Robustness Benchmarking - Arup Mukherjee (1994) There is inherent uncertainty in the operation and reliability of a system in an operating environment. Evaluation of Software Dependability Bev Littlewood
- You can benchmark for performance, but not for dependability. They want a set of tests that one can use to measure, or assess, the dependability, or robustness, of an operating system. The operating system is just an example.
- A robustness benchmarking suite should be...
- portable across platforms
- coverage in that it "tests all possible uses of every system module being tested." advocate random simulation over deterministic tests.
- randomness is good for serendipitously discovering errors, but lacks reproducability.
- extensiability "extend the stimuli in a consistent manner, i.e. simuli can be added to the benchmark in such a way that procues results that are directly comparable with results generated prior to the addition" makes it a concistent measure of progress.
- hierarchy of complexity: do the simple tests first then get more complicated.
- reporting results: guess what you mean by failure and success. Create a scale of failure from system crash to unexpected output. compute an "index of robustness" which is something like a weighted average.
"We would like to be able to claim that we engineer software, in the same sense that we engineer an aero-engine, but most of us would agree that this is not currently an accurate description of our activities. My suspicion is that it never will be."
"In the case of software, there is no physical source of failures, and so none of the reliability theory developed for hardware is relevant. We need new theories that will allow us to achieve required dependability levels, and to evaluate the actual dependability that has been achieved, when the sources of the faults that ultimately result in failure are human intellectual failures."
"If disparity, difficulty, complexity and novelty are so important, why do we not have adequate theories that account for their rôles in software engineering and allow us to control their impact? One reason lies, I think, in our aspiration to be a ‘proper’ engineering discipline, with a genuine scientific underpinning. This laudable aim is too often taken to mean that we must only engage with that which is objective and external to the human - preferably, in fact, with mathematics. Unfortunately, the human element in what we do seems paramount, and any theories that discount it will be doomed to failure. Thus exhortations to ‘mathematise’ software engineering, so as to stay in the world of the logical and deterministic, will at best only address a vanishingly small class of problems, and at worst may give a false confidence to the designers faced with those other real-world problems. My point here, in singling out (some would say caricaturing) a view of formal methods, is not to argue that it has no merit as a means of aiding system design. Rather it is to claim that for almost all real systems the problem of evaluating dependability involves an inherent uncertainty that arises from the potential fallibility of humans when they are faced with solving difficult, novel problems."
More definition of dependability... "The word dependability has come to embrace all those aspects of behaviour upon which the user of a system might need to place dependence: it thus includes reliability, safety, availability and security."
"Measures of dependability are necessarily probabilistic because of an inherent uncertainty. In the case of reliability, for example, this uncertainty in the failure behaviour arises directly from two main sources. In the first place, there is uncertainty about the program itself, inasmuch as we do not know which of the inputs will, when executed, cause failure. Secondly, the operational environment is variable in a nondeterministic way: we cannot say with certainty which inputs will be presented to a program in the future. ... Even if the fix is successful, we do not know the ‘size’ of the fault that has been removed, i.e. there will be uncertainty about the magnitude of the improvement in reliability that will take place even in the event of a perfect fix."
Methods for predicting reliability of a piece of software:
- "estimating and predicting the reliability of a program as it is being debugged during test: the reliability growth problem.... It is often possible to use these techniques to allow a model to ‘learn’ from its past errors and so recalibrate future reliability predictions [Brocklehurst et al. 1990]. The bottom line is that it is usually possible to obtain accurate reliability measures from software reliability growth data, and to know that confidence in such figures is justified."
- "incorporation of structural information about the program into the reliability estimation process...static, the software approach must be dynamic and emulate the way in which software components (modules) are successively exercised in time. This is done by assuming Markovian [Littlewood 1976, Siegrist 1988a, Siegrist 1988b] or semi-Markovian [Littlewood 1976, Littlewood 1979] exchanges of control between modules... The potential advantage of this approach is that it allows the reliability of a system to be predicted before it is built, in the event that it is to be built of modules whose failure history in previous use is
known."
- design diversity. "Estimating the actual degree of dependence in failure behaviour between two ‘diverse’ software versions seems very difficult" (this is what design diversity means "building two or more versions of the required program and allowing an adjudication mechanism (e.g. a voter) to operate at run-time.")
Safety critical systems as the driving factor in reliability research. And the following directions are aimed at ultra high reliability requirements systems...
- a good theory of design diversity.
- A theory for reliance on judgement of an expert in the absence of data.
- Help for designers in early phases of the system design, like, (1) set realistic targets for dependability of components that will result in a dependable system (2) design for validation so you reason about safety (certain events can not occur) using FM and leave reliability to a probabilistic model.
For modest reliability requirements, the following suggestions are offered
- do more experimentation, more solid statitistical analysis, more data collection.
- we don't even understand the efficacy of different methods and practices on the reliability of a system. We'd need large samples of software product developments to collect and corrolate that data. That seems unlikely. Case studies rule the day instead. Even if case studies are the best we'll do, a measuerment framework would help.
- operational reliability depends on the operational environment. Its something of a misnomer to claim that a program has reliability. A program in an environment has reliability.
- Modest reliability under partially observed hostile attacks. [Very interesting since that's what we face today.]
Posted by jones at 07:02 AM | Comments (0)
September 19, 2003
[Education] Simplex algorithm
Posted by jones at 08:23 AM
September 18, 2003
[Research] Dependability links
[Method for Software Dependability Characterization, Patricia Costa and Ioana Rus] describes a work in dependability analysis and metrics, looks interesting and worth a read.
[Dependability.org]
[International Conference on Dependable Systems and Networks]
[Dependability and FM workshop (2001)] William H. Sanders' paper looks relevant
[Challenges and Directions in Depednability (2002)] session 2 on Dependability assessment.
William H. Sanders' paper "Goal: Determine, early in the design phase, the performance, dependability, and performability of large-scale distributed systems. " - need to use alot of different modeling techniques in the determination of dependability (and etc). - propose a framework tool for various formalisms, abstractions and solutions. (slide 6)
- model = abstract representation, formalism = a modeling language, framework = meta language for fomalisms.
- and after that, it looks like you need to read the paper...
Method for Software Dependability Characterization, Patricia Costa and Ioana Rus "Dependability is defined by IFIP WG-10.4 as "The trustworthiness of a computing system which allows reliance to be justifiably placed on the service it delivers". [www.dependability.org]...Dependability also has other definitions, often being regarded as a set of properties such as reliability, availability, safety, fault tolerance, robustness, security, etc." (p2) ""Human performance and human computer interaction are critical elements of software reliability," said Dr. Terry Allard, chief of the Human Factors Research and Technology Division at NASA Ames." (p2) - their high level goal is to "characterize a software system with respect to its dependability properties." then they can use these characterizations to compare dependability during the development cycle (to assess improvement) and compare the effects of "interventions" (p2). - involves lots of discussions, reports, presentations. (p4) (note that NASA/NSF cfp mentions that the designers will be available for consultations during the project). - final report is a description of the "dependability definitions for this particular system" (emphasis added) (p6) that's step 8. - used the "eWorkshop" tool to facilitate online chats, discussions (p8). Note that the Software Testing Fundamentals book mentions that just finding a way to share and revise documents is a significant contribution to the desing of a test plan. - the whole point was to outline a method for meeting with HUMANS to develop a set of dependability metrics for their system that described things that were important to them. - emphasis on baselines for comparision of variants of methods.Posted by jones at 04:10 PM | Comments (0)
[Misc.] SW Dependability Metrics
[Google Search: software dependability metrics] You know its bad when my blog comes up as the number 4 hit on "software dependability metrics" at google.com. That entry is just a close reading of the NSF-NASA CFP, not really that informative yet.
Posted by jones at 02:53 PM | Comments (0)
[Misc.] CS at BYU Idaho
Some links to the CS department at our sister University to the North. [Gregory L. Cameron — Brigham Young University - Idaho, ]
Posted by jones at 01:20 PM | Comments (0)
[Research] A Scalable Test Bench for Chip-set Design Verification
Looks like a pretty straightforward application of verification to an ASIC design. Highlights needs for more random testing, more goal directed stim generation and integration of FV. ASIC designs tend to go faster and have less ROI so I don't understan the arguement for investing in FV for an ASIC design (but that position is based on very little experience. Besides that, I think there's lots of common ground for us to work together to integrate FV into their verificaiton flow and try out directed search stuff. I wonder if they are looking for consultants on a project or new research. Either would certainly benefit our lab.
[Mercer: A Scalable Test Bench for Chip-set Design Verification]
Productivity team = the people who "knit together the right tools"
Rule checking (NOT golden model checking) what does that mean?
Want to...
- increase block level testing
- increase amount of random testing
- decrease effort ot maintain test bench
Watch dogs aka functional coverage.
Future directions are:
- goal direction stimulus generation (we'd call that directed search, I think)
- Integration of formal model checking and equiv checking
- semi-auto gen of system level models.Posted by jones at 08:13 AM | Comments (0)
September 17, 2003
[Misc.] Importing PowerPoint into Latex
Handy for drawing figures in powerpoint for latex documents.
- Install an eps file printer in windows. Install a postscript printer (I use the Apple LaserWriter II NTX). Be sure to sent the printer port to FILE: Fiddle around with the Advanced Options for the printer until you find "document options" and "postscript options" select encapsulated postscript.
- When its time to print your new masterpiece, select your eps file printer. Pick a file name, be sure to save as "all file types" not "printer files (.prn)".
- To include the file in your latex document using the \epsfig command, open the eps file in gsview32 and find the lower left corner and upper right corner of the bounding box your figure. This is done by moving the cursor over the corners and watching the pair of numbers in the bottom left of gsview32.
- The latex command is...
\epsfig{file=yourfile.eps,bbllx=55,bblly=519,bburx=438,bbury=738}where bbllx is the bounding box lower left corner, x coordinate, etc. - that's it.
Posted by jones at 10:38 PM
[Misc.] Other Blog software
Since movable type fails non-gracefully on a full disk and the documentation is a little lacking (though the support fora are nice). It might be time to spend some money on a different package. Here's one option for $50 [pMachine | Publish Your Universe]
Posted by jones at 10:17 PM | Comments (0)
[Misc.] How to Export and Import you Blog
When the disk filled last, the entries database became corrupt. We were fortunate that its still functional, mostly. You may have noticed that "Recent entries" doesn't work any more. Nor does listing your entries to edit them.
We'll need to reset all our blogs in the near future. To export your blog, you just log into the admin interface, click on your blog and then click "import/export" Export is at the bottom of the page. This will create a text file. Save it.
If you've changed your index style sheet (you know who you are), you'll need to cut and paste it to a file somewhere.
To import your blog, obtain the help of a sys admin to:
- copy your exported text file to the archive subdirectory,
- revisit the admin interface,
- re open your blog and click on "import". Import entries as yourself, published. Click import.
- Click "rebuild site" and rebuild each of "Rebuild all files" and "Rebuild Individual Archives only"
- Paste your old stylesheets back into the right style sheet files.
Et voila. You are back in bussiness, again.Posted by jones at 10:11 PM | Comments (0)
September 10, 2003
[From the archive] Slickrock maps & info
[Utah mtn biking, Single-serving, Bandito's, written directions]
Posted by jones at 09:35 PM | Comments (0)
[Misc.] USB flash drives in Linux Labs
Here are the commands:
mount -t vfat /dev/sd?1 < mount point > -o shortname=winnt
The device is /dev/sd?1 where the ? is a, b, c, etc.is
where you are mounting it too. The option gives you long filenames.
I have a feeling that you need to be root to mount it any where but in the
/mnt directory. Good luck. [from Eric Mercer].This is the output thus far.
[jones@karate jones]$ mount /dev/sdb1 ~jones/key -o shortname=winnt
mount: only root can do that
Next up is a trip to the sys opers.Posted by jones at 09:17 AM | Comments (0)
September 08, 2003
[Research] Specification Coverage Aided Test Selection
Pick the input/outputs that haven't been covered yet and visit those first. If no such inputs or outputs are found, then pick at random. Not a direct target for Bayes*, but could be a way to improve the "pick an input at random" behavior if the algorihm ranked covered input/output possibilities based on their probability of leading to an uncovered input/output. Conclude that coverage metrics should be biased toward where the errors are liekly to be found.
[Specification Coverage Aided Test Selection (ResearchIndex), On-the-Fly Conformance Testing Using Spin, de Vries and Tretmans, SPIN '98]
Guided search for coverage in black box conformance testing. Would use an explicit structural heuristic, like Visser, but you don't see the program structure in black box testing.
Implemented in SPIN.
Attempt to minimize the number of test moves, or, the "number of inputs sent to the implementation" and the number of outputs observed.
The heuristic attempts to find an input or output that is uncovered, or has not been excercised (Algorithms 3 and 4). If no such input or output can be found, then the heuristic attempts to find a longer sequence of moves that leads to uncovered inputs or outputs (Algorithm 5). "Algorithm 5 can be seen as a generalization of Aglroithm 4 for deeper 'lookahead' into the set of possible test exectuionts starting from superstate S."The question for us is: How could Bayes* be used to refine their estimates? it appears that the goal is to pick transitions that are garunteed to increase coverage. I don't see a scoring and ranking process in their heuristic. A transition either does or doesn't help coverage. If several do, then they are equiprobable.
Algorithm 4 uses TrueWithProbability(Prob_input). Although Prob_input does not appear defined in Algorithm 4, I think its a measure of the probability that the given input is valid. This could be improved by Bayes*.
If Algorithm 4 fails to find an uncovered input or output from the current superstate and Algorithm 5 fails to find one within the lookahead distance, then Algorithm 3 just picks a random test move. That's the fall back position when nothing absolute was found. That would be a good place to score and rank lookahead states, S', from Algorithm 5 on the "probability that they will result in better coverage." This could, hopefully, do better than random selection when no uncovered moves are found.Three heuristics are used: 0: a random choice of successors from all enabled transitions (I think), 1: pick the uncovered input/output move from current state and 2: lookahead n states to find an uncovered input/output.
The results are given using hundreds of mutations of correct designs and a cummulative chart of detected mutants vs states explored. Very interesting presentation of results. I liked it.
The main conclusion is that "for the coverage based test selection to be truly useful, the used coverage metric should better match the expected failures to be dectected." So, a coverage metic that matches the kinds of errors you want to find is the most useful. The final paragraph emphasises this point again "using some kind of hypothesis of the mutants to be detected by the method to select an appropriate coverage metric." This sounds a lot like "think about where the errors might be, then design a coverage metric to match."
Posted by jones at 08:45 AM | Comments (0)
September 04, 2003
[Research] Guided search for CTL
System-dependent hints guide the expansion of states to reduce the size of intermediate BDDs in symbolic backward reachability analysis. Can obtain complete coverage with fewer computational resources. Property-dependent hints are what we have been using in our guided search. Property-dependent hints guide the serach into error states more quickly. Incidentally, structural-hints (defined in Grove, Visser paper below) guide the search into parts of the graph that are important to verify--regardless of the specific property.
[Symbolic guided search for CTL model checking, Roderick Bloem]
Hints are assertions on the input. Hints can restrict the behavior by pruning transitions out of a state. Hints can over-approximate behavior by allowing any transition that violates the hint to be taken. (page 2).
Hints can be property-dependent. Meaning they guide the search to errors. (p3)
Hints can be system-dependent. Meaning they address computation bottlenecks. (p3)
Only property dependent hints can be used in explicit MC. So system-dependent hints address bottlenecks while resulting in an exhaustive search that required less time/space. This isn't possible in explicit MC becaue the size of the state table is the same in the end either way.
The hints force backward computation to consider only states that results from certain instructions, rather than straying into parts of the state space with complicated dependencies. (sec 4, para 2).
Experimental results are good.Posted by jones at 11:38 AM | Comments (0)
September 01, 2003
[Education] Cognitive Style of powerpoint
Discussion of what kinds of relationships can be expressed with a bulleted list (sequence, priority, set membership)was worth the time--but that information was quoted from an article in the Harvard Bussiness Review. Main points were: don't chop up reasoning with bulleted lists, PowerPoint slides have low information resolution.
Wasn't clear if the problems in the examples were simply faulty reasoning or misapplications of PowerPoint. A thought provoking essay, but didn't deliver on its promise to discuss how to improve PowerPoint presentations. I think he oversimplified the role of the speaker. Most of the analysis was a discussion of slides divorced from their presentation. But that's kind of the point. The slides aren't the presentation.
[Cognitive Style of powerpoint, article from Harvard Bussiness Review]Posted by jones at 04:26 PM | Comments (0)
[Research] Directed Model checking for Java
[Model Checking Java Programs using Structural Heuristics - Groce, Visser (ResearchIndex)]
Rather than converge on errors, the authors converge on coverage. The goal is to explore as many states as possible that satisfy a coverage metric. The justification for this goal is that you don't know beforehand if there is an error and if there is, whether or not it is even reachable. "Structural heuristics attempt to explroe the structure of a program in way conducite finding more general errors"
The heuristic goes something like this:
1. States covering a previously untaken branch recieve the best heuristic value.
2. States recahed by not taking a branch recieve the next best heurstic value.
3. STates that cover a branch alreday taken are ranked according to how many times the branch has been taken (taken more frequently = worse score).
Question: what does it mean for a state to cover a branch? End of page 4 is really the key to the whole thing for covering branches.
The interleaving thread heuristic attempts to reach errors by favoring paths that cause lots of thread switches.
Another hueristic, choose-free, is used in conjunction with abstraction to explore regions of the state space first that are not reduced to non-det by the abstraction.
More blocked does pretty well too. That one measures how many threads are in a blocked state. More threads blocked equals better values.Look at Bloem and Somenzi reference, DAC 2000. Heuristic is inadmissible, but they use A*.
Posted by jones at 02:49 PM | Comments (0)