# Collective Attestation for Manageable IoT Environments
## 6 Evaluation
### Overheads  
**Computation overhead. ** In the attestation phase, each device \(D_{i}\) performs a hash operation for the measurement. We denote the energy cost for the measurement by \(E_{\text{hash}}\). It also needs to generate a MAC on its result, of which energy cost is denoted by \(E_{\text{mac}}\). If the device is not a leaf node, then it has \(|C_{i}|\) children in the attestation tree. Thus, it additionally performs \(|C_{i}|\) MAC validations for aggregating the responses. We assume that the energy costs for MAC generation and validation are the same (\(E_{\text{mac}}\)). Hence, the main energy cost for computation is \(E_{\text{hash}}+(|C_{i}|+1)E_{\text{mac}}\). (We omit the negligible binary operations, such as OR, XOR, or concatenation, in computation overhead.) **Tag size. ** Bloom filters, which are used to generate \(\mathbb{B}\) and \(\Sigma\), have false positives. However, by leveraging the size of Bloom filter, we can limit the false-positive rate. The probability of false positives of \(\Sigma\) can be represented as [41]:  
\[\left(1-e^{-kzn/\ell_{\Sigma}}\right)^{kz}, \tag{1}\]  
where \(k\) hash functions are applied and each device has \(z\) software components. We assume that we use a single hash function (i.e., feature hashing) for each component and \(z=2\). Then, with the negative indication, a 150-byte \(\Sigma\) can contain 15 tags of infected devices in a region while keeping the probability of false positives under 5%. Hence, the tag size is related to how sensitive the region summary is on the individual device information. The tag size means the expected number of identifiable bad provers for the negative indication of attestation, or the expected number of targets for target searching. **Message size. ** A request message carries three parameters: \(N\), \(|A|\), and \(|S|\). There are two kinds of responses in CAMIE: the response to the parent node and the region summary. Thus, each node generates traffic of at least a single response and then a region anchor adds the response traffic for the region summary. We denote by \(w_{i}\) the expected number of region anchors between the initiator and the leaf prover in the attestation tree. It can be summarized as \(w_{i}=\left\lfloor\frac{\log_{C_{i}}|\mathbb{D}|}{|S|}\right\rfloor.\) Thus, the expected message size of request (\(\ell_{\text{req}}\)) and response (\(\ell_{\text{res}}\)) are  
\[\ell_{\text{req}}=\ell_{\text{N}}+\ell_{|\text{A}|}+\ell_{|\text{S}|} \tag{2}\]  
and  
\[\ell_{\text{res}}\leq\left\{(1+w_{i})\cdot(\ell_{\text{B}}+\ell_{\Sigma})+ \ell_{\mathbb{H}}+\ell_{\alpha}+\ell_{\beta}+\ell_{\mathbb{P}}+\ell_{\text{ mac}}\right\}, \tag{3}\]  
respectively. Energy cost.The energy cost for a device shows the overall overhead of the attestation process:  
\[(|C_{i}|\ell_{\mathsf{req}}+\ell_{\mathsf{res}})\,E_{\mathsf{send}}+(\ell_{ \mathsf{req}}+|C_{i}|\ell_{\mathsf{res}})\,E_{\mathsf{recv}}+(1+|C_{i}|)E_{ \mathsf{mac}}+E_{\mathsf{hash}}. \tag{4}\]  
We denote the energy cost to transmit and receive a 1-byte message by \(E_{\mathsf{send}}\) and \(E_{\mathsf{recv}}\), respectively. The device \(D_{i}\) relays a request to all the children and receives the responses from them. Thus, the first two terms of Equation (4) are related to communication overhead. The rest of the terms represent the computation overhead. Note that the energy consumption of a node, Equation (4), is mainly dependent on the number of children and the average height of a region (embedded in \(\ell_{\mathsf{res}}\)). Due to the region summary aggregation, the number of compromised nodes indirectly impacts the communication overhead via the tag size (described later). The initiator has the same energy cost except for the additional signature verification (\(E_{\mathsf{verify}}\)), which also depends on the verification method. Figures 4b and 5 show the energy consumption of CAMIE and the previous schemes, SEDA and SANA. We used the parameters of the system configurations from [19; 21].