ROSE  0.11.145.0
TaintedFlow.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 <Rose/BinaryAnalysis/DataFlow.h>
7 #include <Rose/Diagnostics.h>
8 
9 #include <boost/shared_ptr.hpp>
10 #include <stdexcept>
11 
12 namespace Rose {
13 namespace BinaryAnalysis {
14 
18 class TaintedFlow {
19 public:
24  enum Taintedness { BOTTOM, NOT_TAINTED, TAINTED, TOP };
25 
31  enum Approximation { UNDER_APPROXIMATE, OVER_APPROXIMATE };
32 
37 
39  typedef std::pair<DataFlow::Variable, Taintedness> VariableTaint;
40 
42  // State
44 public:
49  class State {
50  typedef std::list<VariableTaint> VarTaintList;
51  VarTaintList taints_;
52 
53  public:
55  typedef boost::shared_ptr<State> Ptr;
56 
57  protected:
58  // Initialize taintedness for all variables; this is protected because this is a reference-counted object
60  for (const DataFlow::Variable &variable: variables)
61  taints_.push_back(std::make_pair(variable, taint));
62  }
63 
64  public:
70  return State::Ptr(new State(variables, taint));
71  }
72 
76  virtual State::Ptr copy() const {
77  return State::Ptr(new State(*this));
78  }
79 
80  virtual ~State() {}
81 
87 
92 
96  bool merge(const State::Ptr&);
97 
103  const VarTaintList& variables() const { return taints_; }
104  VarTaintList& variables() { return taints_; }
108  void print(std::ostream&) const;
109  };
110 
115 
117  // Transfer function
119 protected:
121  const DataFlow::VertexFlowGraphs &index_; // maps CFG vertex to data flow graph
122  Approximation approximation_;
123  SmtSolverPtr smtSolver_;
125  public:
126  TransferFunction(const DataFlow::VertexFlowGraphs &index, Approximation approx, const SmtSolverPtr &solver,
128  : index_(index), approximation_(approx), smtSolver_(solver), mlog(mlog) {}
129 
130  template<class CFG>
131  StatePtr operator()(const CFG&, size_t cfgVertex, const StatePtr &in) {
132  return (*this)(cfgVertex, in);
133  }
134 
135  StatePtr operator()(size_t cfgVertex, const StatePtr &in);
136 
137  std::string toString(const StatePtr &in);
138  };
139 
141  // Merge function
143 protected:
145  public:
146  bool operator()(StatePtr &dst /*in,out*/, const StatePtr &src) const {
147  ASSERT_not_null(src);
148  if (!dst) {
149  dst = src->copy();
150  return true; // destination changed
151  }
152  return dst->merge(src);
153  }
154  };
155 
157  // Data members
159 private:
160  static Sawyer::Message::Facility mlog;
161  Approximation approximation_;
162  DataFlow dataFlow_;
163  DataFlow::VertexFlowGraphs vertexFlowGraphs_;
164  DataFlow::VariableList variableList_;
165  bool vlistInitialized_;
166  std::vector<StatePtr> results_;
167  SmtSolverPtr smtSolver_;
168 
169 public:
177  : approximation_(UNDER_APPROXIMATE), dataFlow_(userDispatcher), vlistInitialized_(false) {}
178 
182  static void initDiagnostics();
183 
192  Approximation approximation() const { return approximation_; }
193  void approximation(Approximation a) { approximation_ = a; }
202  SmtSolverPtr smtSolver() const { return smtSolver_; }
203  void smtSolver(const SmtSolverPtr &solver) { smtSolver_ = solver; }
211  template<class CFG>
212  void computeFlowGraphs(const CFG &cfg, size_t cfgStartVertex) {
213  using namespace Diagnostics;
214  ASSERT_this();
215  ASSERT_require(cfgStartVertex < cfg.nVertices());
216  Stream mesg(mlog[WHERE] <<"computeFlowGraphs starting at CFG vertex " <<cfgStartVertex);
217  vertexFlowGraphs_ = dataFlow_.buildGraphPerVertex(cfg, cfgStartVertex);
218  variableList_ = dataFlow_.getUniqueVariables(vertexFlowGraphs_);
219  results_.clear();
220  vlistInitialized_ = true;
221  mesg <<"; found " <<StringUtility::plural(variableList_.size(), "variables") <<"\n";
222  if (mlog[DEBUG]) {
223  for (const DataFlow::Variable &variable: variableList_)
224  mlog[DEBUG] <<" found variable: " <<variable <<"\n";
225  }
226  }
227 
236  ASSERT_this();
237  return vertexFlowGraphs_;
238  }
240  using namespace Diagnostics;
241  ASSERT_this();
242  vertexFlowGraphs_ = graphMap;
243  variableList_ = dataFlow_.getUniqueVariables(vertexFlowGraphs_);
244  vlistInitialized_ = true;
245  results_.clear();
246  mlog[WHERE] <<"vertexFlowGraphs set by user with " <<StringUtility::plural(variableList_.size(), "variables") <<"\n";
247  }
255  ASSERT_this();
256  ASSERT_require2(vlistInitialized_, "TaintedFlow::computeFlowGraphs must be called before TaintedFlow::variables");
257  return variableList_;
258  }
259 
264  StatePtr stateInstance(Taintedness taint) const {
265  ASSERT_this();
266  ASSERT_require2(vlistInitialized_, "TaintedFlow::computeFlowGraphs must be called before TaintedFlow::stateInstance");
267  return State::instance(variableList_, taint);
268  }
269 
273  template<class CFG>
274  void runToFixedPoint(const CFG &cfg, size_t cfgStartVertex, const StatePtr &initialState) {
275  using namespace Diagnostics;
276  ASSERT_this();
277  ASSERT_require(cfgStartVertex < cfg.nVertices());
278  ASSERT_not_null(initialState);
279  Stream mesg(mlog[WHERE] <<"runToFixedPoint starting at CFG vertex " <<cfgStartVertex);
280  results_.clear();
281  TransferFunction xfer(vertexFlowGraphs_, approximation_, smtSolver_, mlog);
284  dfEngine.name("tainted-flow");
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
const VertexStates & getFinalStates() const
All outgoing states.
Definition: DataFlow.h:517
StatePtr getFinalState(size_t cfgVertexId) const
Query results.
Definition: TaintedFlow.h:294
static State::Ptr instance(const DataFlow::VariableList &variables, Taintedness taint=BOTTOM)
Allocating constructor.
Definition: TaintedFlow.h:69
Approximation
Mode of operation.
Definition: TaintedFlow.h:31
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.
Definition: TaintedFlow.h:103
Collection of streams.
Definition: Message.h:1606
Various tools for performing tainted flow analysis.
Definition: TaintedFlow.h:18
void runToFixedPoint(const CFG &cfg, size_t cfgStartVertex, const StatePtr &initialState)
Run data flow.
Definition: TaintedFlow.h:274
void runToFixedPoint()
Run data-flow until it reaches a fixed point.
Definition: DataFlow.h:471
std::list< Variable > VariableList
List of variables.
Definition: DataFlow.h:86
void print(std::ostream &) const
Print this state.
boost::shared_ptr< State > Ptr
Shared-ownership pointer to taint states.
Definition: TaintedFlow.h:55
Main namespace for the ROSE library.
bool merge(const State::Ptr &)
Merge other state into this state.
bool setIfExists(const DataFlow::Variable &, Taintedness)
Set taintedness if the variable exists.
boost::shared_ptr< Dispatcher > DispatcherPtr
Shared-ownership pointer to a semantics instruction dispatcher.
VariableList getUniqueVariables(const VertexFlowGraphs &)
Get list of unique variables.
State::Ptr StatePtr
Reference counting pointer to State.
Definition: TaintedFlow.h:114
VarTaintList & variables()
List of all variables and their taintedness.
Definition: TaintedFlow.h:104
void vertexFlowGraphs(const DataFlow::VertexFlowGraphs &graphMap)
Property: data flow graphs.
Definition: TaintedFlow.h:239
std::pair< DataFlow::Variable, Taintedness > VariableTaint
Variable-Taintedness pair.
Definition: TaintedFlow.h:39
static Taintedness merge(Taintedness, Taintedness)
Merges two taint values.
const std::string & name() const
Property: Name for debugging.
Definition: DataFlow.h:372
const DataFlow::VertexFlowGraphs & vertexFlowGraphs() const
Property: data flow graphs.
Definition: TaintedFlow.h:235
TaintedFlow(const InstructionSemantics::BaseSemantics::DispatcherPtr &userDispatcher)
Constructs a tainted flow analysis.
Definition: TaintedFlow.h:176
const DataFlow::VariableList & variables() const
List of variables.
Definition: TaintedFlow.h:254
void smtSolver(const SmtSolverPtr &solver)
Property: SMT solver.
Definition: TaintedFlow.h:203
static void initDiagnostics()
Initialize diagnostics.
Various tools for data-flow analysis.
Definition: DataFlow.h:69
SmtSolverPtr smtSolver() const
Property: SMT solver.
Definition: TaintedFlow.h:202
std::shared_ptr< SmtSolver > SmtSolverPtr
Reference counting pointer.
void approximation(Approximation a)
Property: approximation.
Definition: TaintedFlow.h:193
Taintedness & lookup(const DataFlow::Variable &)
Find the taintedness for some variable.
Approximation approximation() const
Property: approximation.
Definition: TaintedFlow.h:192
VertexFlowGraphs buildGraphPerVertex(const CFG &cfg, size_t startVertex, VertexUnpacker vertexUnpacker)
Compute data-flow per CFG vertex.
Definition: DataFlow.h:171
virtual State::Ptr copy() const
Virtual copy constructor.
Definition: TaintedFlow.h:76
StatePtr stateInstance(Taintedness taint) const
Creates a new state.
Definition: TaintedFlow.h:264
void computeFlowGraphs(const CFG &cfg, size_t cfgStartVertex)
Compute data flow graphs.
Definition: TaintedFlow.h:212