ROSE  0.11.31.0
BinaryTaintedFlow.h
1 #ifndef ROSE_BinaryAnalysis_TaintedFlow_H
2 #define ROSE_BinaryAnalysis_TaintedFlow_H
3 #include <featureTests.h>
4 #ifdef ROSE_ENABLE_BINARY_ANALYSIS
5 
6 #include "BinaryDataFlow.h"
7 #include "Diagnostics.h"
8 
9 #include <boost/foreach.hpp>
10 #include <boost/shared_ptr.hpp>
11 #include <stdexcept>
12 
13 namespace Rose {
14 namespace BinaryAnalysis {
15 
19 class TaintedFlow {
20 public:
25  enum Taintedness { BOTTOM, NOT_TAINTED, TAINTED, TOP };
26 
32  enum Approximation { UNDER_APPROXIMATE, OVER_APPROXIMATE };
33 
38 
40  typedef std::pair<DataFlow::Variable, Taintedness> VariableTaint;
41 
43  // State
45 public:
50  class State {
51  typedef std::list<VariableTaint> VarTaintList;
52  VarTaintList taints_;
53 
54  public:
56  typedef boost::shared_ptr<State> Ptr;
57 
58  protected:
59  // Initialize taintedness for all variables; this is protected because this is a reference-counted object
61  BOOST_FOREACH (const DataFlow::Variable &variable, variables)
62  taints_.push_back(std::make_pair(variable, taint));
63  }
64 
65  public:
71  return State::Ptr(new State(variables, taint));
72  }
73 
77  virtual State::Ptr copy() const {
78  return State::Ptr(new State(*this));
79  }
80 
81  virtual ~State() {}
82 
88 
93 
97  bool merge(const State::Ptr&);
98 
104  const VarTaintList& variables() const { return taints_; }
105  VarTaintList& variables() { return taints_; }
109  void print(std::ostream&) const;
110  };
111 
116 
118  // Transfer function
120 protected:
122  const DataFlow::VertexFlowGraphs &index_; // maps CFG vertex to data flow graph
123  Approximation approximation_;
124  SmtSolverPtr smtSolver_;
126  public:
127  TransferFunction(const DataFlow::VertexFlowGraphs &index, Approximation approx, const SmtSolverPtr &solver,
129  : index_(index), approximation_(approx), smtSolver_(solver), mlog(mlog) {}
130 
131  template<class CFG>
132  StatePtr operator()(const CFG &cfg, size_t cfgVertex, const StatePtr &in) {
133  return (*this)(cfgVertex, in);
134  }
135 
136  StatePtr operator()(size_t cfgVertex, const StatePtr &in);
137 
138  std::string toString(const StatePtr &in);
139  };
140 
142  // Merge function
144 protected:
146  public:
147  bool operator()(StatePtr &dst /*in,out*/, const StatePtr &src) const {
148  ASSERT_not_null(src);
149  if (!dst) {
150  dst = src->copy();
151  return true; // destination changed
152  }
153  return dst->merge(src);
154  }
155  };
156 
158  // Data members
160 private:
161  static Sawyer::Message::Facility mlog;
162  Approximation approximation_;
163  DataFlow dataFlow_;
164  DataFlow::VertexFlowGraphs vertexFlowGraphs_;
165  DataFlow::VariableList variableList_;
166  bool vlistInitialized_;
167  std::vector<StatePtr> results_;
168  SmtSolverPtr smtSolver_;
169 
170 public:
178  : approximation_(UNDER_APPROXIMATE), dataFlow_(userDispatcher), vlistInitialized_(false) {}
179 
183  static void initDiagnostics();
184 
193  Approximation approximation() const { return approximation_; }
194  void approximation(Approximation a) { approximation_ = a; }
203  SmtSolverPtr smtSolver() const { return smtSolver_; }
204  void smtSolver(const SmtSolverPtr &solver) { smtSolver_ = solver; }
212  template<class CFG>
213  void computeFlowGraphs(const CFG &cfg, size_t cfgStartVertex) {
214  using namespace Diagnostics;
215  ASSERT_this();
216  ASSERT_require(cfgStartVertex < cfg.nVertices());
217  Stream mesg(mlog[WHERE] <<"computeFlowGraphs starting at CFG vertex " <<cfgStartVertex);
218  vertexFlowGraphs_ = dataFlow_.buildGraphPerVertex(cfg, cfgStartVertex);
219  variableList_ = dataFlow_.getUniqueVariables(vertexFlowGraphs_);
220  results_.clear();
221  vlistInitialized_ = true;
222  mesg <<"; found " <<StringUtility::plural(variableList_.size(), "variables") <<"\n";
223  if (mlog[DEBUG]) {
224  BOOST_FOREACH (const DataFlow::Variable &variable, variableList_)
225  mlog[DEBUG] <<" found variable: " <<variable <<"\n";
226  }
227  }
228 
237  ASSERT_this();
238  return vertexFlowGraphs_;
239  }
241  using namespace Diagnostics;
242  ASSERT_this();
243  vertexFlowGraphs_ = graphMap;
244  variableList_ = dataFlow_.getUniqueVariables(vertexFlowGraphs_);
245  vlistInitialized_ = true;
246  results_.clear();
247  mlog[WHERE] <<"vertexFlowGraphs set by user with " <<StringUtility::plural(variableList_.size(), "variables") <<"\n";
248  }
256  ASSERT_this();
257  ASSERT_require2(vlistInitialized_, "TaintedFlow::computeFlowGraphs must be called before TaintedFlow::variables");
258  return variableList_;
259  }
260 
265  StatePtr stateInstance(Taintedness taint) const {
266  ASSERT_this();
267  ASSERT_require2(vlistInitialized_, "TaintedFlow::computeFlowGraphs must be called before TaintedFlow::stateInstance");
268  return State::instance(variableList_, taint);
269  }
270 
274  template<class CFG>
275  void runToFixedPoint(const CFG &cfg, size_t cfgStartVertex, const StatePtr &initialState) {
276  using namespace Diagnostics;
277  ASSERT_this();
278  ASSERT_require(cfgStartVertex < cfg.nVertices());
279  ASSERT_not_null(initialState);
280  Stream mesg(mlog[WHERE] <<"runToFixedPoint starting at CFG vertex " <<cfgStartVertex);
281  results_.clear();
282  TransferFunction xfer(vertexFlowGraphs_, approximation_, smtSolver_, mlog);
285  dfEngine.runToFixedPoint(cfgStartVertex, initialState);
286  results_ = dfEngine.getFinalStates();
287  mesg <<"; results for " <<StringUtility::plural(results_.size(), "vertices", "vertex") <<"\n";
288  }
289 
294  StatePtr getFinalState(size_t cfgVertexId) const {
295  ASSERT_this();
296  ASSERT_require(cfgVertexId < results_.size());
297  return results_[cfgVertexId];
298  }
299 };
300 
301 std::ostream& operator<<(std::ostream &out, const TaintedFlow::State &state);
302 
303 } // namespace
304 } // namespace
305 
306 #endif
307 #endif
StatePtr getFinalState(size_t cfgVertexId) const
Query results.
static State::Ptr instance(const DataFlow::VariableList &variables, Taintedness taint=BOTTOM)
Allocating constructor.
std::string plural(T n, const std::string &plural_phrase, const std::string &singular_phrase="")
Helpful way to print singular or plural words.
const VarTaintList & variables() const
List of all variables and their taintedness.
Collection of streams.
Definition: Message.h:1606
Various tools for performing tainted flow analysis.
void runToFixedPoint(const CFG &cfg, size_t cfgStartVertex, const StatePtr &initialState)
Run data flow.
std::list< Variable > VariableList
List of variables.
TaintedFlow(const InstructionSemantics2::BaseSemantics::DispatcherPtr &userDispatcher)
Constructs a tainted flow analysis.
void print(std::ostream &) const
Print this state.
boost::shared_ptr< State > Ptr
Shared-ownership pointer to taint states.
Main namespace for the ROSE library.
void runToFixedPoint()
Run data-flow until it reaches a fixed point.
bool merge(const State::Ptr &)
Merge other state into this state.
bool setIfExists(const DataFlow::Variable &, Taintedness)
Set taintedness if the variable exists.
VariableList getUniqueVariables(const VertexFlowGraphs &)
Get list of unique variables.
boost::shared_ptr< Dispatcher > DispatcherPtr
Shared-ownership pointer to a semantics instruction dispatcher.
State::Ptr StatePtr
Reference counting pointer to State.
VarTaintList & variables()
List of all variables and their taintedness.
void vertexFlowGraphs(const DataFlow::VertexFlowGraphs &graphMap)
Property: data flow graphs.
std::pair< DataFlow::Variable, Taintedness > VariableTaint
Variable-Taintedness pair.
static Taintedness merge(Taintedness, Taintedness)
Merges two taint values.
const DataFlow::VertexFlowGraphs & vertexFlowGraphs() const
Property: data flow graphs.
const DataFlow::VariableList & variables() const
List of variables.
void smtSolver(const SmtSolverPtr &solver)
Property: SMT solver.
static void initDiagnostics()
Initialize diagnostics.
Various tools for data-flow analysis.
SmtSolverPtr smtSolver() const
Property: SMT solver.
void approximation(Approximation a)
Property: approximation.
Taintedness & lookup(const DataFlow::Variable &)
Find the taintedness for some variable.
Approximation approximation() const
Property: approximation.
VertexFlowGraphs buildGraphPerVertex(const CFG &cfg, size_t startVertex, VertexUnpacker vertexUnpacker)
Compute data-flow per CFG vertex.
virtual State::Ptr copy() const
Virtual copy constructor.
std::shared_ptr< class SmtSolver > SmtSolverPtr
Reference-counting pointer for SMT solvers.
StatePtr stateInstance(Taintedness taint) const
Creates a new state.
const VertexStates & getFinalStates() const
All outgoing states.
void computeFlowGraphs(const CFG &cfg, size_t cfgStartVertex)
Compute data flow graphs.