  Ability to test firmware on embedded devices is critical to discovering
vulnerabilities prior to their adversarial exploitation. State-of-the-art
automated testing methods rehost firmware in emulators and attempt to
facilitate inputs from a diversity of methods (interrupt driven, status
polling) and a plethora of devices (such as modems and GPS units). Despite
recent progress to tackle peripheral input generation challenges in rehosting,
a firmware's expectation of multi-byte magic values supplied from peripheral
inputs for string operations still pose a significant roadblock. We solve the
impediment posed by multi-byte magic strings in monolithic firmware. We propose
feedback mechanisms for input-to-state mapping and retaining seeds for targeted
replacement mutations with an efficient method to solve multi-byte comparisons.
The feedback allows an efficient search over a combinatorial solution-space. We
evaluate our prototype implementation, SplITS, with a diverse set of 21
real-world monolithic firmware binaries used in prior works, and 3 new binaries
from popular open source projects. SplITS automatically solves 497% more
multi-byte magic strings guarding further execution to uncover new code and
bugs compared to state-of-the-art. In 11 of the 12 real-world firmware binaries
with string comparisons, including those extensively analyzed by prior works,
SplITS outperformed, statistically significantly. We observed up to 161%
increase in blocks covered and discovered 6 new bugs that remained guarded by
string comparisons. Significantly, deep and difficult to reproduce bugs guarded
by comparisons, identified in prior work, were found consistently. To
facilitate future research in the field, we release SplITS, the new firmware
data sets, and bug analysis at https://github.com/SplITS-Fuzzer
