[uml-devel] UML and Execution Replay

[uml-devel] UML and Execution Replay

[Oliver Oppitz]

Hello *,

I have a new project proposal for applying UML in the deterministic (!) 
debugging of parallel programs.

This concept is not new and called execution-replay (ER): the behaviour of 
a (complicated, multi-threaded, buggy) program is recorded during an 
*execution* phase. Later during a *replay* phase the exact behaviour is 
reproduced -- including the bugs. Therefore the system is ideal to debug - 
rarely occuring bugs in parallel systems, - race conditions, - any sort of 
bugs that are (nearly) impossible to reproduce. All you need to do is to 
record the behaviour once and then simply replay and debug it! Sounds 
exciting? - you must be a hacker then ;-) And think of the consequences...
 The role of UML will be a replayable virtual machine. By recording all 
input to the UML keyboard, network, ... and feeding this same input into 
the UML during replay, the exact internal behaviour will be reproduced. One 
gets ER without modifying the code of the applications program. This is a 
huge advantage over conventional approaches that require that the software 
adheres strictly to certain protocols. Also the overhead should be minimal.

There is some more to the idea though. I presented a paper "A particular 
bug trap: Execution replay for Virtual machines" on this idea at a 
conference last week (http://aadebug2003.elis.rug.ac.be/). See link below.

I am working on the implementation myself but of course: any help is 
welcome. I will put up a small website in the next weeks and post again. If 
anyone is interested in the project already, get in contact with me via 
o.oppitz at gmx d O T net. I'd be happy to share my ideas.

Regards,

  Oliver


The paper "A particular bug trap: Execution replay for Virtual machines" 
can be found at http://213.203.244.62/paper.short.pdf
http://213.203.244.62/paper.long.pdf
Note, that there is a way to work around the limitations of the Intel 
architecture mentioned in the paper. So I am pursuing this project on x86.

Further information on Execution replay can be found at
http://www.zealcore.com/
http://www.mrtc.mdh.se/projects/getProject.php3?id=0044
The approach is different but already applied in an industrial context 
(VxWorks).





-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

Re: [uml-devel] UML and Execution Replay

[George Washington Dunlap III]

Hello!  I just found this thread, and I thought you might be interested in 
our work on ReVirt:
  http://www.eecs.umich.edu/CoVirt/umlinux.html

Basically, last year we started a project with UMLinux (now FAUMachine,
from the University of Erlangen), to do complete VM logging and replay
using the performance counters.  We presented our work in December at
OSDI:

George W. Dunlap, Samuel T. King, Sukru Cinar, Murtaza Basrai, and Peter 
M. Chen.  ReVirt: Enabling Intrusion Analysis through Virtual-Machine 
Logging and Replay.  In Proceedings of the 2002 Symposium on Operating 
Systems Design and Implementation (OSDI), pags 211-224, December 2002.

Our main goal with ReVirt is security, not debugging; we have a paper 
about backtracking intrusions in this year's SOSP:

Samuel T. King and Peter M. Chen.  Backtracking Intrusions.  To appear in 
the Proceedings of the 19th ACM Symposium on Operating Systems Principles, 
November 2003.

We're now working to port our system over to Jeff Dike's UML.  It's a bit
more challenging: UMLinux is only a single process, so as long as we
re-deliver interrupts in the same way and answer system calls in the same
way, everything works.  UML is a bit more difficult because there are
multiple processes, and issues with shared memory and the host kernel
system calls.  We may have to make a few minor changes to UML to get 
ReVirt working, but we should have a basic system running in a month or 
two.

So, it looks like you're planning on doing your replay system in a 
different way than we are.  Do you want to do your work on your own 
system, or would you like to start with ours?  BackTracker already has 
some hooks for GDB, but I don't know exactly how they work (that's Sam 
King's area).  We're planning on focusing on security, so I don't think 
we'd be in competition if you were going to do debugging.

Anyway, let me know what you think, and keep us informed of how your work 
is coming along.  We'd be interested in how other ways of doing replay 
pan out.

Peace,
 -George

On Tue, 16 Sep 2003, Oliver Oppitz wrote:

> Hello *,
> 
> I have a new project proposal for applying UML in the deterministic (!) 
> debugging of parallel programs.
> 
> This concept is not new and called execution-replay (ER): the behaviour of 
> a (complicated, multi-threaded, buggy) program is recorded during an 
> *execution* phase. Later during a *replay* phase the exact behaviour is 
> reproduced -- including the bugs. Therefore the system is ideal to debug - 
> rarely occuring bugs in parallel systems, - race conditions, - any sort of 
> bugs that are (nearly) impossible to reproduce. All you need to do is to 
> record the behaviour once and then simply replay and debug it! Sounds 
> exciting? - you must be a hacker then ;-) And think of the consequences...
>  The role of UML will be a replayable virtual machine. By recording all 
> input to the UML keyboard, network, ... and feeding this same input into 
> the UML during replay, the exact internal behaviour will be reproduced. One 
> gets ER without modifying the code of the applications program. This is a 
> huge advantage over conventional approaches that require that the software 
> adheres strictly to certain protocols. Also the overhead should be minimal.
> 
> There is some more to the idea though. I presented a paper "A particular 
> bug trap: Execution replay for Virtual machines" on this idea at a 
> conference last week (http://aadebug2003.elis.rug.ac.be/). See link below.
> 
> I am working on the implementation myself but of course: any help is 
> welcome. I will put up a small website in the next weeks and post again. If 
> anyone is interested in the project already, get in contact with me via 
> o.oppitz at gmx d O T net. I'd be happy to share my ideas.
> 
> Regards,
> 
>   Oliver
> 
> 
> The paper "A particular bug trap: Execution replay for Virtual machines" 
> can be found at http://213.203.244.62/paper.short.pdf
> http://213.203.244.62/paper.long.pdf
> Note, that there is a way to work around the limitations of the Intel 
> architecture mentioned in the paper. So I am pursuing this project on x86.
> 
> Further information on Execution replay can be found at
> http://www.zealcore.com/
> http://www.mrtc.mdh.se/projects/getProject.php3?id=0044
> The approach is different but already applied in an industrial context 
> (VxWorks).
> 
> 
> 
> 
> 
> -------------------------------------------------------
> This sf.net email is sponsored by:ThinkGeek
> Welcome to geek heaven.
> http://thinkgeek.com/sf
> _______________________________________________
> User-mode-linux-devel mailing list
> User-mode-linux-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel
> 

-- 
+-------------------+----------------------------------------
| dunlapg@umich.edu | http://www-personal.umich.edu/~dunlapg 
+-------------------+----------------------------------------
| ...there be many, many ancient systems in the world, and it 
| is the decree of the dreaded god Murphy that thy next 
| employment just might be on one.  While thou sleepest, he 
| plotteth against thee.  Awake and take care.
|   - Henry Spencer, "The Ten Commandments for C Programmers"
+------------------------------------------------------------
| Outlaw Junk Email! Support HR 1748 (www.cauce.org)





-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

Re: [uml-devel] UML and Execution Replay

[Nuno Silva]

Hi George!
(We exchanged a few emails regarding CoVirt/ReVirt some months ago ;)


George Washington Dunlap III wrote:
> Hello!  I just found this thread, and I thought you might be interested in 
> our work on ReVirt:
>   http://www.eecs.umich.edu/CoVirt/umlinux.html
> 

A few days ago this address was offline. Now it's back online but when I 
try to download the tgz:

Not Found
The requested URL /CoVirt/revirt-dist-072003a.tgz was not found on this 
server.

Just to let you know ;)

Regards,
Nuno Silva




-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

Re: [uml-devel] UML and Execution Replay

[George Washington Dunlap III]

Sorry for the halfway-OT posts: if you want to hear more of this 
discussion, e-mail me and I'll make sure to cc you.

FYI, our departmental web server had a disk crash a few days ago, and
they're working to restore the files from tape backup.  It should be back 
up in a few days.

In the mean time, I posted a mirror on my own personal site:
	http://www.gospeljam.org/misc/revirt-dist-072003a.tgz 
This contains our modified host kernel, modified UMLinux kernel, a README
and a basic environment to get things running.  Let me know if you have 
any questions.

Again, sorry for the noise -- last one I'll send 'till I have a UML
version of ReVirt to announce (or some implementation questions to
discuss).  =)

Peace,
 -George

On Wed, 17 Sep 2003, Nuno Silva wrote:

> Hi George!
> (We exchanged a few emails regarding CoVirt/ReVirt some months ago ;)
> 
> 
> George Washington Dunlap III wrote:
> > Hello!  I just found this thread, and I thought you might be interested in 
> > our work on ReVirt:
> >   http://www.eecs.umich.edu/CoVirt/umlinux.html
> > 
> 
> A few days ago this address was offline. Now it's back online but when I 
> try to download the tgz:
> 
> Not Found
> The requested URL /CoVirt/revirt-dist-072003a.tgz was not found on this 
> server.
> 
> Just to let you know ;)
> 
> Regards,
> Nuno Silva
> 
> 

-- 
+-------------------+----------------------------------------
| dunlapg@umich.edu | http://www-personal.umich.edu/~dunlapg 
+-------------------+----------------------------------------
| ...there be many, many ancient systems in the world, and it 
| is the decree of the dreaded god Murphy that thy next 
| employment just might be on one.  While thou sleepest, he 
| plotteth against thee.  Awake and take care.
|   - Henry Spencer, "The Ten Commandments for C Programmers"
+------------------------------------------------------------
| Outlaw Junk Email! Support HR 1748 (www.cauce.org)




-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

Re: [uml-devel] UML and Execution Replay

[Oliver Oppitz]

"Patrick \"Petschge\" Kilian" <petschge@web.de> 
> The only problem is, that you have to replay the input with the exact 
> correct timing.

Yes, indeed that is the more tricky part. However, there are known techniques for handling this. One involves a hardware instruction counter. Using this you can record exactly in what moment some input (e.g. an interrupt) was received. Hardware instruction counters in current CPUs are however pretty imprecise, in particular in x86. Motorola PowerPC 7410 is pretty precise.

An alternative technique is called "unique marker". When there is an interrupt you record some checksums over the register file, parts of the stack etc. For the replay you insert breakpoint instructions at all places where an interrupt had occured in the execution phase. By comparing the stored checksum with the current register file/stack you can determine "where" in the program flow you are. Obviously there is potential for ambiguity but not much. It works in practice. Henrik Thane at the MRTC (Mälardalen Real Time Research Center, http://www.mrtc.mdh.se/) works on this. 

Because I want to work on x86 I favour the latter approach. 

Regards, Oliver

______________________________________________________________________________
Es geht nicht  mehr ohne Handy, aber geht es auch guenstiger?
Ja, mit Call by Call vom Handy. http://handybycall.web.de/?mc=021103



-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

Re: [uml-devel] UML and Execution Replay

[Lars Marowsky-Bree]

On 2003-09-17T09:45:31,
   Oliver Oppitz <o.oppitz@web.de> said:

Have you checked out Werner Almesberger work on "umlsim"?


Sincerely,
    Lars Marowsky-Brée <lmb@suse.de>

-- 
High Availability & Clustering		ever tried. ever failed. no matter.
SuSE Labs				try again. fail again. fail better.
Research & Development, SuSE Linux AG		-- Samuel Beckett



-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

Re: [uml-devel] UML and Execution Replay

[George Washington Dunlap III]

On Wed, 17 Sep 2003, Oliver Oppitz wrote:

> Yes, indeed that is the more tricky part. However, there are known
> techniques for handling this. One involves a hardware instruction
> counter. Using this you can record exactly in what moment some input
> (e.g. an interrupt) was received. Hardware instruction counters in
> current CPUs are however pretty imprecise, in particular in x86.
> Motorola PowerPC 7410 is pretty precise.

There are other counts you can use instead, however.  For instance, <eip,
branch count> tuples, or <memory writes, [register state]>.  The
instruction counters on P4s and AMDs are imprecise, but the P4 counter
named "retired_branch_type" is very accurate.  On the AMDs, they have a
branch counter which is accurate as well, but unfortunately also counts 
hardware interrupts and software exceptions: including page faults and 
math coprocessor exceptions (for lazy FPU sharing).  You just have to 
instrument the host kernel to count these and subtract them off, and 
you're golden.

We've been using these counters on the AMD for over a year, and the P4 for 
several months, all with extensive testing, and had no problems replaying.

> An alternative technique is called "unique marker". When there is an
> interrupt you record some checksums over the register file, parts of the
> stack etc. For the replay you insert breakpoint instructions at all
> places where an interrupt had occured in the execution phase. By
> comparing the stored checksum with the current register file/stack you
> can determine "where" in the program flow you are. Obviously there is
> potential for ambiguity but not much. It works in practice. Henrik Thane
> at the MRTC (Mälardalen Real Time Research Center,
> http://www.mrtc.mdh.se/) works on this.

This sounds like an interesting idea.  Our focus is security, however, 
so there are two problems with that idea.  First, though accidental 
ambiguity may be unlikely, an attacker can craft state that will be 
ambiguous and thwart your replaying system.  

Secondly, if you get an interrupt on the millionth iteration of an
extermely tight loop, you have to set the breakpoint one million times,
which is incredibly slow.  (UMLinux measuring the BogoMIPS, for instance,
took less than a second to log, and an hour to replay.)  With the
performance counters, the P4 and AMD have a feature where you can set the
counters to a negative number and get an interrupt when it overflows.  
This isn't 100% precise (because of deep pipelines, etc) but it will get
you within about 100 branches, and you can breakpoint from there.

Are there any similar optimizations for the unique marker approach?

> Because I want to work on x86 I favour the latter approach. 

The former can be made to work on x86, we've done it quite robustly. =)  
E-mail me if you want some help.

 -George

-- 
+-------------------+----------------------------------------
| dunlapg@umich.edu | http://www-personal.umich.edu/~dunlapg 
+-------------------+----------------------------------------
| ...there be many, many ancient systems in the world, and it 
| is the decree of the dreaded god Murphy that thy next 
| employment just might be on one.  While thou sleepest, he 
| plotteth against thee.  Awake and take care.
|   - Henry Spencer, "The Ten Commandments for C Programmers"
+------------------------------------------------------------
| Outlaw Junk Email! Support HR 1748 (www.cauce.org)



-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

Re: [uml-devel] UML and Execution Replay

[Oliver Oppitz]

Lars Marowsky-Bree <lmb@suse.de> schrieb am 17.09.03 11:20:35:
> Have you checked out Werner Almesberger work on "umlsim"?

Not yet. Looks interesting and seems to go into the same direction. I'll contact him.

Thanks for the hint!

  Oliver

______________________________________________________________________________
Die Besten ihrer Klasse! WEB.DE FreeMail (1,7) und WEB.DE Club (1,9) -
bei der Stiftung Warentest - ein Doppelsieg! http://f.web.de/?mc=021184



-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

RE: [uml-devel] UML and Execution Replay

[Wichmann, Mats D]

> Lars Marowsky-Bree <lmb@suse.de> schrieb am 17.09.03 11:20:35:
> > Have you checked out Werner Almesberger work on "umlsim"?
> 
> Not yet. Looks interesting and seems to go into the same 
> direction. I'll contact him.
> 
> Thanks for the hint!

Werner is presenting on umlsim at Linux-Kongress
in Saarbrücken in about a month if that's of 
interest...


-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

Re: [uml-devel] UML and Execution Replay

[Jeff Dike]

mats.d.wichmann@intel.com said:
> Werner is presenting on umlsim at Linux-Kongress in Saarbrücken in
> about a month if that's of  interest... 

He also presented at OLS a couple of months ago, so checking those proceedings
might be of interest.

				Jeff



-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

RE: [uml-devel] UML and Execution Replay

[Wichmann, Mats D]

> mats.d.wichmann@intel.com said:
> > Werner is presenting on umlsim at Linux-Kongress in Saarbrücken in
> > about a month if that's of  interest... 
> 
> He also presented at OLS a couple of months ago, so checking 
> those proceedings might be of interest.

Indeed.  I found it complex enough that it helped
to hear him speak about it in person, though, and
Oliver has a .de email address so I thought that
might be a nice opportunity (Jeff will also
be speaking at Linux-Kongress, by the way).


-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

RE: [uml-devel] UML and Execution Replay

[Oliver Oppitz]

Thanks for the hint. Seems a great occasion to talk to a lot of interesting people...

 Oliver

"Wichmann, Mats D" <mats.d.wichmann@intel.com> schrieb am 18.09.03 13:22:36:
> 
> 
> > mats.d.wichmann@intel.com said:
> > > Werner is presenting on umlsim at Linux-Kongress in Saarbrücken in
> > > about a month if that's of  interest... 
> > 
> > He also presented at OLS a couple of months ago, so checking 
> > those proceedings might be of interest.
> 
> Indeed.  I found it complex enough that it helped
> to hear him speak about it in person, though, and
> Oliver has a .de email address so I thought that
> might be a nice opportunity (Jeff will also
> be speaking at Linux-Kongress, by the way).
> 
> 
> -------------------------------------------------------
> This sf.net email is sponsored by:ThinkGeek
> Welcome to geek heaven.
> http://thinkgeek.com/sf
> _______________________________________________
> User-mode-linux-devel mailing list
> User-mode-linux-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel


______________________________________________________________________________
Doppelsieg fur WEB.DE FreeMail und Club bei Stiftung Warentest!
Beste Sicherheitswertung und Verfuegbarkeit! http://f.web.de/?mc=021181



-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
User-mode-linux-devel mailing list
User-mode-linux-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel