1 /*
2  * Copyright (C) 2018 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #include "src/tracing/core/packet_stream_validator.h"
18 
19 #include <inttypes.h>
20 #include <stddef.h>
21 
22 #include "perfetto/base/logging.h"
23 #include "perfetto/ext/base/utils.h"
24 #include "perfetto/protozero/proto_utils.h"
25 
26 #include "protos/perfetto/trace/trace_packet.pbzero.h"
27 
28 namespace perfetto {
29 
30 namespace {
31 
32 using protozero::proto_utils::ProtoWireType;
33 
34 const uint32_t kReservedFieldIds[] = {
35     protos::pbzero::TracePacket::kTrustedUidFieldNumber,
36     protos::pbzero::TracePacket::kTrustedPacketSequenceIdFieldNumber,
37     protos::pbzero::TracePacket::kTraceConfigFieldNumber,
38     protos::pbzero::TracePacket::kTraceStatsFieldNumber,
39     protos::pbzero::TracePacket::kCompressedPacketsFieldNumber,
40     protos::pbzero::TracePacket::kSynchronizationMarkerFieldNumber,
41 };
42 
43 // This translation unit is quite subtle and perf-sensitive. Remember to check
44 // BM_PacketStreamValidator in perfetto_benchmarks when making changes.
45 
46 // Checks that a packet, spread over several slices, is well-formed and doesn't
47 // contain reserved top-level fields.
48 // The checking logic is based on a state-machine that skips the fields' payload
49 // and operates as follows:
50 //              +-------------------------------+ <-------------------------+
51 // +----------> | Read field preamble (varint)  | <----------------------+  |
52 // |            +-------------------------------+                        |  |
53 // |              |              |            |                          |  |
54 // |       <Varint>        <Fixed 32/64>     <Length-delimited field>    |  |
55 // |          V                  |                      V                |  |
56 // |  +------------------+       |               +--------------+        |  |
57 // |  | Read field value |       |               | Read length  |        |  |
58 // |  | (another varint) |       |               |   (varint)   |        |  |
59 // |  +------------------+       |               +--------------+        |  |
60 // |           |                 V                      V                |  |
61 // +-----------+        +----------------+     +-----------------+       |  |
62 //                      | Skip 4/8 Bytes |     | Skip $len Bytes |-------+  |
63 //                      +----------------+     +-----------------+          |
64 //                               |                                          |
65 //                               +------------------------------------------+
66 class ProtoFieldParserFSM {
67  public:
68   // This method effectively continuously parses varints (either for the field
69   // preamble or the payload or the submessage length) and tells the caller
70   // (the Validate() method) how many bytes to skip until the next field.
Push(uint8_t octet)71   size_t Push(uint8_t octet) {
72     varint_ |= static_cast<uint64_t>(octet & 0x7F) << varint_shift_;
73     if (octet & 0x80) {
74       varint_shift_ += 7;
75       if (varint_shift_ >= 64) {
76         // Do not invoke UB on next call.
77         varint_shift_ = 0;
78         state_ = kInvalidVarInt;
79       }
80       return 0;
81     }
82     uint64_t varint = varint_;
83     varint_ = 0;
84     varint_shift_ = 0;
85 
86     switch (state_) {
87       case kFieldPreamble: {
88         uint64_t field_type = varint & 7;  // 7 = 0..0111
89         auto field_id = static_cast<uint32_t>(varint >> 3);
90         // Check if the field id is reserved, go into an error state if it is.
91         for (size_t i = 0; i < base::ArraySize(kReservedFieldIds); ++i) {
92           if (field_id == kReservedFieldIds[i]) {
93             state_ = kWroteReservedField;
94             return 0;
95           }
96         }
97         // The field type is legit, now check it's well formed and within
98         // boundaries.
99         if (field_type == static_cast<uint64_t>(ProtoWireType::kVarInt)) {
100           state_ = kVarIntValue;
101         } else if (field_type ==
102                    static_cast<uint64_t>(ProtoWireType::kFixed32)) {
103           return 4;
104         } else if (field_type ==
105                    static_cast<uint64_t>(ProtoWireType::kFixed64)) {
106           return 8;
107         } else if (field_type ==
108                    static_cast<uint64_t>(ProtoWireType::kLengthDelimited)) {
109           state_ = kLenDelimitedLen;
110         } else {
111           state_ = kUnknownFieldType;
112         }
113         return 0;
114       }
115 
116       case kVarIntValue: {
117         // Consume the int field payload and go back to the next field.
118         state_ = kFieldPreamble;
119         return 0;
120       }
121 
122       case kLenDelimitedLen: {
123         if (varint > protozero::proto_utils::kMaxMessageLength) {
124           state_ = kMessageTooBig;
125           return 0;
126         }
127         state_ = kFieldPreamble;
128         return static_cast<size_t>(varint);
129       }
130 
131       case kWroteReservedField:
132       case kUnknownFieldType:
133       case kMessageTooBig:
134       case kInvalidVarInt:
135         // Persistent error states.
136         return 0;
137 
138     }          // switch(state_)
139     return 0;  // To keep GCC happy.
140   }
141 
142   // Queried at the end of the all payload. A message is well-formed only
143   // if the FSM is back to the state where it should parse the next field and
144   // hasn't started parsing any preamble.
valid() const145   bool valid() const { return state_ == kFieldPreamble && varint_shift_ == 0; }
state() const146   int state() const { return static_cast<int>(state_); }
147 
148  private:
149   enum State {
150     kFieldPreamble = 0,  // Parsing the varint for the field preamble.
151     kVarIntValue,        // Parsing the varint value for the field payload.
152     kLenDelimitedLen,    // Parsing the length of the length-delimited field.
153 
154     // Error states:
155     kWroteReservedField,  // Tried to set a reserved field id.
156     kUnknownFieldType,    // Encountered an invalid field type.
157     kMessageTooBig,       // Size of the length delimited message was too big.
158     kInvalidVarInt,       // VarInt larger than 64 bits.
159   };
160 
161   State state_ = kFieldPreamble;
162   uint64_t varint_ = 0;
163   uint32_t varint_shift_ = 0;
164 };
165 
166 }  // namespace
167 
168 // static
Validate(const Slices & slices)169 bool PacketStreamValidator::Validate(const Slices& slices) {
170   ProtoFieldParserFSM parser;
171   size_t skip_bytes = 0;
172   for (const Slice& slice : slices) {
173     for (size_t i = 0; i < slice.size;) {
174       const size_t skip_bytes_cur_slice = std::min(skip_bytes, slice.size - i);
175       if (skip_bytes_cur_slice > 0) {
176         i += skip_bytes_cur_slice;
177         skip_bytes -= skip_bytes_cur_slice;
178       } else {
179         uint8_t octet = *(reinterpret_cast<const uint8_t*>(slice.start) + i);
180         skip_bytes = parser.Push(octet);
181         i++;
182       }
183     }
184   }
185   if (skip_bytes == 0 && parser.valid())
186     return true;
187 
188   PERFETTO_DLOG("Packet validation error (state %d, skip = %zu)",
189                 parser.state(), skip_bytes);
190   return false;
191 }
192 
193 }  // namespace perfetto
194