Model Checking

I've become very interested in abstract interpretation and model checking recently. The limitations of traditional testing (specifically: you can only try so many combinations of inputs) are starting to bother me, and so I'm looking for new techniques. Abstract interpretation seems to offer a whole new set of possibilities for testing, and I've been studying it for the past couple months.

Here's a very readable introduction to the kinds of things you can do with model checking, written by the people at Coverity. Coverity is a startup based on the technique.

Here's a paper describing the java bytecode verifier as an abstract interpreter.

The BLAST project at Berkeley seems to have made some significant progress in this area. Their work seems to have led to projects like the Static Driver Verifier at Microsoft, which "finds bugs in device drivers at compile time". Their use of boolean programs (programs whose variables keep track of the current value of various boolean predicates) is very interesting. I wish I was more familiar with software theorem provers so that I could understand their work better.

I'm currently playing around with writing an abstract interpreter for java bytecode. If that works out, I'd like to try working with the assembler output from c++ programs (since the c++ language model is too complicated to work with directly). My current goal is to try to use abstract interpretation to automatically recover equivalence classes from code. For example, a statement like "if (x < 10) ..." would indicate that there are two equivalence classes for x: (x<10) and (x>=10).

It would probably be a better use of my time to just try to learn out to use the BLAST tool, but I want to have a more hands-on understanding of the techniques involved. I'm currently at the point where it has become obvious why the monotonicity requirement for fixpoint computation is necessary -- otherwise you might never terminate when faced with a loop. I've also become comfortable with the idea of least-upper-bounds as a technique for handling branches and joins. Previously I hadn't been able to figure out how to organize my data structures so that they could handle loops.

Followups to Model Checking:

Posted on February 21, 2005 09:20 PM
More testing articles

Comments

http://pag.csail.mit.edu/daikon/

Posted by: Jay McCarthy at February 22, 2005 06:35 AM

Yes, I thought of mentioning Daikon. But daikon is a runtime invariant detector, while abstract interpretation and model checking are static tools.

In particular, daikon knows nothing about code that never gets executed by your unit tests. In contrast, model checkers include even untested paths when constructing their proofs.

Posted by: Kim at February 22, 2005 01:57 PM

You would loose a lot of type information using the assembly output (besides the question of, which architecture? SPARC? MIPS? x86?). You can recover simple types like characters, integers, floats and pointers but objects? It's a pointer to memory. Also, at the assembly level (and I'll pick the MC68K as an example), your statement of:

if (x < 10)

will most likely be translated to:

move.l [a6 + 12],d0
cmp.l #10,d0
bls.w ...

At that point, you have two equivilence classes, the four bytes at [a6+12] < 10, and the four bytes at [a6+12] >= 10---probably an integer, but careful tracking would be needed for the following:

move.l [a6+8],d0
and.l d0,d0
beq.w ...

are we doing something like:

if (x == 0)

or

if (pointer == NULL)

I'm not saying it's impossible, just that dropping down to assembly may be too low of a level for this.

Posted by: Sean Conner at February 22, 2005 05:03 PM

Sean, the debugging information should have enough information to recover any type info that you might need. I admit that it's entirely possible that assembler is too low level. But even still, it seems like a more feasible approach than attempting to parse C++ in the first place. If I had to parse C++, I'd probably try to find some way of reusing the gcc front-end.

Posted by: Kim at February 23, 2005 01:11 PM

Hi! I like your srticle and I would like very much to read some more information on this issue. Will you post some more?
As we know , we can find lots of fans ,lots of store have been open worldwide.

Posted by: Nightfall Ugg Boots at October 31, 2009 12:41 AM

Hi! I like your srticle and I would like very much to read some more information on this issue. Will you post some more?
As we know , we can find lots of fans ,lots of store have been open worldwide.

Posted by: Nightfall Ugg Boots at October 31, 2009 12:41 AM

People all over the world know the abercrombie and fitch,but not everyone really knows how fashion the abercrombie is,hollister is the Legend maker. Everybody wears the hollister clothing would be the abercrombie mensand the abercrombie womens, if you want know you can search the Ruehl No.925 or abercrombie outlet in the www.google.com .

Posted by: fitch at November 14, 2009 01:48 AM

Uggs on sale now.UGG Classic Cardy Boot makes me different form the other

girls. The UGG Bailey Button Boot is a good choice for female.

Posted by: ugg classic cardy boots at November 17, 2009 12:37 AM

UGG Bailey Button bootsis a new style in 2009.The classic cardy uggs boots is another hot boots that worth of buying.And the classic tall ugg boots will make your winter amusing.And now uggs on sale,if you are looking for such a boot,the ugg boots is good choice this year.

Posted by: UGG Bailey Button Boots at November 17, 2009 01:08 AM

I started wearing Ugg boots a couple of years ago and bought short boots last fall. I wear my Uggs pretty much everyday because I work in an environment where I can dress casually. The product Uggs boots on sale are made from sheepskin. They look like soft.

Posted by: uggs on sale at November 17, 2009 08:41 PM

Tiffany Rings
Tiffany bangles
Tiffany Bracelets

Posted by: Tiffany bangles at November 19, 2009 08:35 PM

We are the best online sales for the china wholesale . Here you can have a large of choices of kinds Ugg Boots,Converse Shoes,Timberland Boots,puma shoes,Nike Shox Shoes ,Nike Dunk SB Shoes,Nike Air Max,Links Of London,Tiffany Jewelry,Dior Handbags?,jimmy choo handbags ,Cartier Watches, 8GB Mp4 Players,Bluetooth Car DVDs. All our cheap online cheap goods are high quality and original packages, and best service. We offer our customers the best service, 7 days arrive at your door.Enjoy your easy and happy shopping with us.

Posted by: cheap goods sale. at November 20, 2009 01:27 AM

Laptop Battery Laptop Battery Laptop Batteries
Laptop Batteries discount laptop battery
discount laptop battery
notebook battery notebook battery
computer battery computer battery
replacement laptop battery replacement laptop battery
notebook batteries notebook batteries

Posted by: Laptop Battery at November 24, 2009 09:50 PM

MagicStix - MagicStix
One Tech Site - Information Technology News, Tutorials, Tips and Tricks
The Forex Page - The Foreign Exchange
Indonesia Page - All About Indonesia
Guam Page - Island of Guam

Posted by: magicstix at November 26, 2009 02:33 PM

MagicStix - MagicStix
One Tech Site - Information Technology News, Tutorials, Tips and Tricks
The Forex Page - The Foreign Exchange
Indonesia Page - All About Indonesia
Guam Page - Island of Guam

Posted by: magicstix at November 26, 2009 02:35 PM

MagicStix - MagicStix
One Tech Site - Information Technology News, Tutorials, Tips and Tricks
The Forex Page - The Foreign Exchange
Indonesia Page - All About Indonesia
Guam Page - Island of Guam

Posted by: magicstix at November 26, 2009 02:48 PM

Spring is near,every girl wants to be the bride in the special season.They are eager to put on beautiful Wedding Dresses or the Bridal gowns.During the day the Wedding gowns is the good choose,and the night,if you want radiant,you need the Evening gowns.
About the bridesmaid,they have to wear Bridesmaid Dresses in order to avoid grab limelight with the bride.And the Flower Girl has the Flower Girl Dresses,too.In the wedding,the Cocktail Dresses and the Evening Dresses is necessary,too!And remember,the Wedding Dress of the Bridal Dress must be the most glaring!

Posted by: weddingdressclub at December 1, 2009 01:32 AM

In order to welcome the approaching Christmas and to thank for the customer,there are amazing ugg boots sale promotions on our company.Once you buy one of ugg 30th anniversary,ugg nightfall,ugg coquette,ugg lo pro button or ugg knightsbridge other ugg boots on our website, we will give you a gift for free. http://www.uggboots4buy.com/

Posted by: ugg knightsbridge at December 1, 2009 03:49 AM

If a man join together to pursuit knowledge, no one can take it from him.cheap nfl jersys Books are to human beings which as nba jerseys sale emory to the individuanl nhl Jerseys.We cannot change anything mlb jerseys unless we learn and accept it, Damn does not liberate it, it oppresses.A classic adidas jerseys book which people praise but don't read.A man dies still if he has done nothing, as one who has done football child jerseys much.Education is something which remains ofter one has forgotten everything football jerseys he learned in school.Education is something remains ofter one has forgotten everything he learned in school.http://www.nfljerseymlb.com/

Posted by: discount nfl jersey at December 1, 2009 03:55 AM

Thanks for the awesome information.To celebrate Christmas,there are great sale promotions on http://nikejordanshoes2sell.com/,all of our products such as cheap air jordan men shoes,af1 shoes,nike nz shoes or ed hardy high boots ,d&g high boots are on sale,ugg sundance II boots low price,high quaility.Time limited!come on to get what you want!

Posted by: nike dunk SB at December 1, 2009 08:58 AM

Thank you for the great job,it help me so much!With christmas approaching,our website http://www.onestop-onlineshopping.com/are on sale promotion,you can find all of our christian louboutin high boots,ugg 30th anniversary and cheap jodan shoes low price but also high quality.more products such as nike shox nz shoes on sale ,d&g men high cut boots, are showing to you.There must be something you would need!

Posted by: Christiaon Louboutian boots at December 1, 2009 08:59 AM

Thank you for the message supplyer!There are amazing ugg ultra tall ,ugg sundance II and cheap ugg night fall sale promotions on our company to thank for the customer of http://www.uggboots2buy.com/ and to embrace the coming Christmas. You can Get one gift free once you buy an ugg boots,such as cheap ugg classic crochet or ugg bailey button on sale on our website. Action is louder than speak. Hurry up and you may be the first one to get the gift.

Posted by: ugg boots at December 1, 2009 09:00 AM

[url=http://www.northfaceoutletsale.com/] North Face Down Jacket [/url]
[url=http://www.northfacesalestore.com/] North Face Down Jacket [/url]

[url=http://www.northfaceoutletsale.com/] North Face Down Jacket [/url]
[url=http://www.northfacesalestore.com/] North Face Down Jacket [/url]

Posted by: north face jacket at December 2, 2009 07:37 AM





无标题文档


North Face Down Jacket





无标题文档


North Face Down Jacket






无标题文档


North Face Down Jacket





无标题文档


North Face Down Jacket

Posted by: north face jacket at December 2, 2009 07:38 AM





无标题文档


North Face Down Jacket

Posted by: north face jacket at December 2, 2009 07:39 AM

[link=http://www.northfaceoutletsale.com/] North Face Down Jacket [/link]
[link=http://www.northfacesalestore.com/] North Face Down Jacket [/link]

Posted by: north face jacket at December 2, 2009 07:39 AM

The latest discount North Face Down Jacket for sale,we work as Kid North Face Down Jacket dealer prodive all types of North Face product.Pricing and Free shipping here.http://www.northfacesaleoutlet.com is right here at your service!

Posted by: north face jacket at December 2, 2009 07:39 AM

The latest discount North Face Down Jacket for sale,we work as Kid North Face Down Jacket dealer prodive all types of North Face product.Pricing and Free shipping here.http://www.northfacesaleoutlet.com is right here at your service!

Posted by: north face jacket at December 2, 2009 07:40 AM

You should go to www.uggssky.com who want to buy cheap ugg boots ,classic tall boots, short tall and bailey boots,buy youself or your friedns a pair of ugg boots for the christmas!

Posted by: ugg classic boots on sale at December 2, 2009 12:52 PM

You should go to www.uggssky.com who want to buy cheap ugg boots ,classic tall boots, short tall and bailey boots,buy youself or your friedns a pair of ugg boots for the christmas!

Posted by: ugg classic boots on sale at December 2, 2009 12:54 PM

One Simple Tech - Computer News, Reviews and Guides
The Forex Page - The Foreign Exchange
The Airlines Page - All Things Airlines
The Fitness Page - Guides to Healty Life
The Network Site - Networking Technology
The Adsense Site - Guide to Online Adsense Earning
The Asian Hotties - Sexy Asian Girls
Bali Page - Island of Bali
Guam Page - Island of Guam
Kalakas 671 - All About Island of Guam
Indonesia Page - All About Indonesia
MagicStix Site - Personal Blog of MagicStix
Permai's Page - Personal Blog of Permai

Posted by: Indonesia at December 2, 2009 08:29 PM

One Simple Tech - Computer News, Reviews and Guides
The Forex Page - The Foreign Exchange
The Airlines Page - All Things Airlines
The Fitness Page - Guides to Healty Life
The Network Site - Networking Technology
The Adsense Site - Guide to Online Adsense Earning
The Asian Hotties - Sexy Asian Girls
Bali Page - Island of Bali
Guam Page - Island of Guam
Kalakas 671 - All About Island of Guam
Indonesia Page - All About Indonesia
MagicStix Site - Personal Blog of MagicStix
Permai's Page - Personal Blog of Permai

Posted by: Indonesia at December 2, 2009 08:30 PM

Merry Christmas ! Go to puma store buy a pair of puma sneakers that have a nice holiday, cat puma,Ferrari puma and Women's Puma Speed Cat etc cheap puma shoes are the best gift for christmas,go on!

Posted by: buy cheap puma shoes on puma store at December 3, 2009 07:00 AM
Post a comment









Remember info?




Prove you're human. Type "human":