Trace-based schedulability analysis to enhance passive side-channel attack resilience of embedded software

Side channel attacks (SCAs) are a practical threat to the security of cryptographic implementations. A well known countermeasure against them is to alter the temporal location of instructions among different executions of the code. In this work we provide an algorithm to generate valid schedules of block cipher implementations. The proposed algorithm relies on a trace-theory based analysis and efficiently generates any valid schedule of the implementation under exam, selecting the ones with higher diversity among them. The algorithm was implemented as a pass in the backend of the LLVM compiler suite, and the results of the automated instruction scheduling are provided to validate its effectiveness as an SCA countermeasure employing the whole ISO standard block cipher suite.