01: //
02: // Copyright (C) 2005 United States Government as represented by the
03: // Administrator of the National Aeronautics and Space Administration
04: // (NASA). All Rights Reserved.
05: //
06: // This software is distributed under the NASA Open Source Agreement
07: // (NOSA), version 1.3. The NOSA has been approved by the Open Source
08: // Initiative. See the file NOSA-1.3-JPF at the top of the distribution
09: // directory tree for the complete NOSA document.
10: //
11: // THE SUBJECT SOFTWARE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY OF ANY
12: // KIND, EITHER EXPRESSED, IMPLIED, OR STATUTORY, INCLUDING, BUT NOT
13: // LIMITED TO, ANY WARRANTY THAT THE SUBJECT SOFTWARE WILL CONFORM TO
14: // SPECIFICATIONS, ANY IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR
15: // A PARTICULAR PURPOSE, OR FREEDOM FROM INFRINGEMENT, ANY WARRANTY THAT
16: // THE SUBJECT SOFTWARE WILL BE ERROR FREE, OR ANY WARRANTY THAT
17: // DOCUMENTATION, IF PROVIDED, WILL CONFORM TO THE SUBJECT SOFTWARE.
18: //
19: package gov.nasa.jpf.search;
20:
21: import gov.nasa.jpf.*;
22: import gov.nasa.jpf.util.Debug;
23:
24: /**
25: * this is a straight execution pseudo-search - it doesn't search at
26: * all (i.e. it doesn't backtrack), but just behaves like a 'normal' VM,
27: * going forward() until there is no next state then it restarts the search
28: * until it hits a certain number of paths executed
29: *
30: */
31: public class RandomSearch extends AbstractSearch {
32: int path_limit = 0;
33:
34: public RandomSearch(Config config, VM vm) {
35: super (config, vm);
36:
37: path_limit = config.getInt("search.RandomSearch.path_limit", 0);
38:
39: System.out.println("Path Limit = " + path_limit);
40:
41: Debug.println(Debug.WARNING, "Random Search");
42: }
43:
44: public void search() {
45: int depth = 0;
46: int paths = 0;
47: depth++;
48:
49: if (hasPropertyTermination()) {
50: return;
51: }
52:
53: vm.forward();
54: VMState init_state = vm.getState();
55: init_state.makeRestorable();
56:
57: notifySearchStarted();
58: while (!done) {
59: if (vm.forward()) {
60: notifyStateAdvanced();
61: if (hasPropertyTermination()) {
62: return;
63: }
64: depth++;
65: } else { // no next state
66: // <2do> we could check for more things here. If the last insn wasn't
67: // the main return, or a System.exit() call, we could flag a JPFException
68: isPropertyViolated();
69: done = (paths >= path_limit);
70: paths++;
71: System.out.println("paths = " + paths);
72: depth = 1;
73: vm.restoreState(init_state);
74: //vm.rewind();
75: }
76: }
77: notifySearchFinished();
78: }
79: }
|