Об упрощении выражений со смешанной битовой и целочисленной арифметикой

Выражения со смешанной булевой и целочисленной арифметикой (далее — MBA-выражения, от англ. Mixed Boolean- Arithmetic) от $t$ целочисленных $n$-битных переменных часто находят применение при обфускации (запутывании) программного кода. Запутывание заключается в замене коротких выражений более длинными эквивалентными выражениями, на исследование которых, как представляется, аналитиком может быть затрачено больше времени. В работе показано, что для упрощения линейных MBA-выражений (сокращения количества слагаемых) может быть применена техника, аналогичная технике декодирования линейных кодов по информационным совокупностям. На основе этой техники в работе построены алгоритмы упрощения линейных MBA-выражений: алгоритм нахождения выражения с минимальным числом слагаемых и алгоритм сокращения числа слагаемых. На основе алгоритма сокращения числа слагаемых построен алгоритм, позволяющий оценить стойкость MBA-выражения к упрощению. В работе экспериментально оценена зависимость среднего числа слагаемых в линейном MBA-выражении, возвращаемом алгоритмами упрощения, от разрядности $n$, числа итераций декодирования и мощности набора булевых функций, по которому ищется линейная комбинация с минимальным числом ненулевых коэффициентов. Результаты экспериментов для всех рассмотренных $t$ и $n$ показывают, что если до обфускации линейное MBA-выражение содержало $r=1,2,3$ слагаемых, то разработанные алгоритмы упрощения с вероятностью, близкой к единице, позволяют по обфусцированному варианту этого выражения найти эквивалентное с числом слагаемых не более $r$. В этом заключается главное отличие техники декодирования по информационным совокупностям от известных техник упрощения линейных MBA-выражений, в которых целью является сокращение числа слагаемых до не более чем $2^t$. В работе также установлено, что для случайно сгенерированных линейных MBA-выражений с ростом $n$ среднее число слагаемых в возвращаемом выражении стремится к $2^t$ и не отличается от среднего числа слагаемых в линейном выражении, возвращаемом известными алгоритмами упрощения. Полученные результаты, в частности, позволяют определить $t$ и $n$, для которых количество слагаемых в упрощенном линейном MBA-выражении в среднем будет не менее заданного.

1. B. Barak et al., “On the (im)possibility of obfuscating programs,” in Advances in Cryptology — CRYPTO 2001, 2001, vol. 2139, pp. 1–18.

2. Y. Zhou, A. Main, Y. X. Gu, and H. Johnson, “Information hiding in software with mixed boolean-arithmetic transforms,” in Information Security Applications. WISA 2007, 2007, vol. 4867, pp. 61–75.

3. S. Gulwani, O. Polozov, and R. Singh, “Program synthesis,” Foundations and Trends in Programming Languages, vol. 4, no. 1-2, pp. 1–119, 2017.

4. B. Reichenwallner and P. Meerwald-Stadler, “Efficient Deobfuscation of Linear Mixed Boolean-Arithmetic Expressions,” in Proceedings of the 2022 ACM Workshop on Research on offensive and defensive techniques in the context of Man At The End (MATE) attacks, 2022, pp. 19–28.

5. L. Zobernig, “Mathematical Aspects of Program Obfuscation,” PhD thesis, The University of Auckland, 2020.

6. P. Garba and M. Favaro, “Saturn-software deobfuscation framework based on LLVM,” in Proceedings of the 3rd ACM Workshop on Software Protection, 2019, pp. 27–38.

7. N. Eyrolles, “Obfuscation with Mixed Boolean-Arithmetic Expressions: reconstruction, analysis and simplification tools,” PhD thesis, Universit'e Paris-Saclay, 2017.

8. D. Xu et al., “Boosting SMT solver performance on mixed-bitwise-arithmetic expressions,” in Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, 2021, pp. 651–664.

9. B. Liu, J. Shen, J. Ming, Q. Zheng, J. Li, and D. Xu, “MBA-Blast: Unveiling and Simplifying Mixed Boolean-Arithmetic Obfuscation,” in Proceedings of the 30th USENIX Security Symposium, 2021, pp. 1701–1718.

10. E. Berlekamp, R. McEliece, and H. Van Tilborg, “On the inherent intractability of certain coding problems (corresp.),” IEEE Transactions on Information Theory, vol. 24, no. 3, pp. 384–386, 1978.

11. E. Prange, “The use of information sets in decoding cyclic codes,” IRE Transactions on Information Theory, vol. 8, no. 5, pp. 5–9, 1962.

12. C. Peters, “Information-set decoding for linear codes over $mathbbF_q$,” in Post-Quantum Cryptography. PQCrypto 2010, 2010, vol. 6061, pp. 81–94.

13. V. Weger, N. Gassner, and J. Rosenthal, “A survey on code-based cryptography.” 2022.