hphp/runtime/vm/taint/state.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #pragma once
  18
  19 #ifdef HHVM_TAINT
  20
  21 #include "hphp/runtime/base/tv-val.h"
  22 #include "hphp/runtime/vm/func.h"
  23 #include "hphp/util/arena.h"
  24
  25 #include <chrono>
  26 #include <map>
  27 #include <memory>
  28 #include <optional>
  29 #include <set>
  30 #include <vector>
  31
  32 #include "hphp/runtime/vm/taint/configuration.h"
  33
  34 template <>
  35 struct std::hash<HPHP::tv_lval> {
  36   std::size_t operator()(const HPHP::tv_lval& val) const {
  37     return val.hash();
  38   }
  39 };
  40
  41 namespace HPHP {
  42 namespace taint {
  43
  44 /*
  45  * Single hop in a trace. Can be from callee to caller on trace from source
  46  * to root; or caller to callee on trace from root to sink.
  47  */
  48 struct Hop {
  49   const Func* from;
  50   const Func* to;
  51 };
  52
  53 typedef ArenaImpl<32768> PathArena;
  54 /*
  55  * A Path is a full trace.
  56  *
  57  * This datastructure is optimized for writes at the expense of reads.
  58  * We expect a single tainted value may flow to many others, so we emulate
  59  * a tree structure ourselves to make adding children cheap.
  60  *
  61  * We assume all pointers to Paths are kept alive by the caller.
  62  */
  63 struct Path {
  64   std::string jsonLine() const;
  65
  66   // Creates a new, empty Path
  67   Path();
  68
  69   // Creates a new path originating here
  70   static Path* origin(PathArena* arena, Hop hop);
  71
  72   // Creates a path going from this path to the new hop
  73   // Takes an allocator to help with memory management
  74   Path* to(PathArena* arena, Hop hop) const;
  75
  76   ~Path() = default;
  77
  78  private:
  79   // The hop taken here. Can be empty for the root (both pointers null)
  80   Hop hop;
  81   const Path* parent;
  82 };
  83
  84 using Value = Path*;
  85
  86 /**
  87  * Use a stack based on a dequeue with a fixed size
  88  * (based on HHVM's VM stack size) to avoid allocating
  89  * after creation.
  90  */
  91 struct Stack {
  92   Stack();
  93
  94   void push(Value value);
  95   void pushFront(Value value);
  96
  97   Value top() const;
  98   Value peek(int offset) const;
  99
 100   void pop(int n = 1);
 101   void popFront();
 102   void replaceTop(Value value);
 103
 104   size_t size() const;
 105   std::string show() const;
 106
 107   void clear();
 108
 109  private:
 110   bool full() const;
 111   bool empty() const;
 112   std::vector<Value> m_stack;
 113   size_t m_top;
 114   size_t m_bottom;
 115 };
 116
 117 /*
 118  * Our shadow heap is not replicating the full VM heap but keeps track
 119  * of tainted values (cells) on the heap.
 120  *
 121  * We keep a few different heaps around, for modeling different types
 122  * of things on the heap.
 123  */
 124
 125 // Model locals, which are identified by `tv_lval`s
 126 struct LocalsHeap {
 127   void set(tv_lval typedValue, Value value);
 128   Value get(const tv_lval& typedValue) const;
 129
 130   void clear();
 131
 132  private:
 133   hphp_fast_map<tv_lval, Value> m_heap;
 134 };
 135
 136 // Model objects, which are identified by `tv_lval`s
 137 // and have their properties identified by strings.
 138 struct ObjectsHeap {
 139   void set(ObjectData* object, folly::StringPiece property, Value value);
 140   Value get(ObjectData* object, folly::StringPiece property) const;
 141
 142   void clear();
 143
 144  private:
 145   hphp_fast_map<ObjectData*, folly::F14FastMap<std::string, Value>> m_heap;
 146 };
 147
 148 // Model collections, which are identified by `tv_lval`s.
 149 // We just store whether the whole collection is tainted or not right now,
 150 // and do not support un-tainting on removal.
 151 struct CollectionsHeap {
 152   void set(tv_lval typedValue, Value value);
 153   Value get(const tv_lval& typedValue) const;
 154
 155   void clear();
 156
 157  private:
 158   hphp_fast_map<tv_lval, Value> m_heap;
 159 };
 160
 161 // Model classes, which are identified by `Class*`s
 162 // and have their static properties identified by strings.
 163 struct ClassesHeap {
 164   void set(Class* klass, folly::StringPiece property, Value value);
 165   Value get(Class* klass, folly::StringPiece property) const;
 166
 167   void clear();
 168
 169  private:
 170   hphp_fast_map<Class*, folly::F14FastMap<std::string, Value>> m_heap;
 171 };
 172
 173 struct State {
 174   static rds::local::RDSLocal<State, rds::local::Initialize::FirstUse> instance;
 175
 176   State();
 177
 178   void initialize();
 179   void teardown();
 180
 181   std::vector<Source> sources(const Func* func);
 182   std::vector<Sink> sinks(const Func* func);
 183
 184   Stack stack;
 185   LocalsHeap heap_locals;
 186   ObjectsHeap heap_objects;
 187   CollectionsHeap heap_collections;
 188   ClassesHeap heap_classes;
 189
 190   // Arena to hold all the paths
 191   std::unique_ptr<PathArena> arena;
 192   // Contains all the taint flows found in this request
 193   std::vector<Path*> paths;
 194
 195   std::shared_ptr<FunctionMetadataTracker> m_function_metadata = nullptr;
 196
 197   std::chrono::time_point<std::chrono::system_clock> m_request_start;
 198 };
 199
 200 } // namespace taint
 201 } // namespace HPHP
 202
 203 #endif