Обфускация

Обфуска́ция программы, всякое её преобразование, которое сохраняет вычисляемую программой функцию (эквивалентное преобразование), но при этом придает программе такую форму, что извлечение из текста программы (исходного кода) ключевой информации об алгоритмах и структурах данных, реализованных в этой программе, становится трудоёмкой задачей.

Обфускация программ преследует цель затруднить понимание программ и воспрепятствовать целенаправленной их модификации. Поэтому задачу обфускации программ можно воспринимать как одну из задач системного программирования, подобную другим задачам преобразования программ: трансляции (компиляции), оптимизации, реорганизации, распараллеливания. С другой стороны, обфускацию можно также рассматривать как особую разновидность шифрования программ. В отличие от традиционных видов шифрования обфускация не предполагает построения эффективных алгоритмов расшифрования, т. е. восстановления исходного текста программы, но зато требует сохранения смысла зашифрованного сообщения – функции, вычисляемой обфускируемой программой. Поэтому задача обфускации программ может быть также отнесена к области криптографии и криптоанализа. Именно двойственность этой задачи и объясняет тот факт, что её исследование вот уже более 20 лет проводится по двум направлениям: со стороны системного программирования и со стороны криптографии, которые очень мало взаимодействуют друг с другом. Обфускация сравнительно новый раздел информатики.

Впервые (без использования самого термина «обфускация») это понятие возникло в 1976 г. в работе Диффи и Хеллмана (Diffie. 1976.^[1] P. 644–654). Они заметили, что введённое ими понятие криптосистем с открытым ключом позволяет преобразовывать некоторые схемы вычисления с секретным ключом в стойкие криптографические схемы с открытым ключом. А собственно понятие обфускации программ впервые введено в работе Коллберга (Collberg), где обфускация представлялась эффективным средством защиты интеллектуальной собственности. Эти две статьи стали началом двух направлений исследований обфускации программ, а именно обфускации для решения криптографических задач и обфускации для решения задач в области программного обеспечения и кибербезопасности.

Основные характеристики проблемы обфускации программ:

Спектр задач, для решения которых можно было бы использовать алгоритмы обфускации, весьма обширен, и цели применения обфускации могут быть противоположны. Обфускацию можно использовать как для защиты программ от атак (Cohen. 1993.^[2] P. 565–584), так и для маскировки компьютерных вирусов (Chess. 2000; Ször. 2001. P. 123–144). При обфускации программ для нужд криптографии целью маскировки является сокрытие данных (секретного ключа), но не алгоритмов. Но когда методы обфускации применяются для обеспечения безопасности, то целью маскировки является сокрытие алгоритмов, но не обрабатываемых данных. Таким образом, «проблема обфускации программ» включает в себя целое семейство задач маскировки программ, для каждой из которых вводятся специальные требования стойкости обфускации.

Имеется большой разрыв между теоретическими требованиями стойкости обфускации программ и применяемыми на практике методами и средствами решения этой задачи. Известно немало работ, в которых предлагаются различные практические методы обфускации программ; практические методы обфускации программ (подробное описание многих из них см.: Collberg. 2009^[3]). Некоторые из этих методов были реализованы в коммерческих программных продуктах (см., например: Aucsmith. 1996.^[4] P. 317–333; Hamilton. 2011.^[5] P. 1–15; A study of software protection techniques. 2007.^[6] P. 249–253; Jien-Tsai Chan. 2004.^[7] P. 1–10; Jun Ge. 2005. P. 83–92). Однако влияние фундаментальных теоретических результатов [Barak. 2001. P. 1–18 (см. также On the (im)possibility of obfuscating programs 2012.^[8] P. 1–48); Varnovsky. 2004.^[9] P. 127–137; On the concept of software obfuscation ... 2007. P. 281–298; Goldwasser. 2007. P. 194–213] на эту ветвь развития программного обеспечения минимально: требования безопасности, исследуемые в контексте криптографических приложений, либо являются слишком сильными, либо неадекватны тем задачам защиты программного обеспечения, которые возникают на практике.

Имеется большой разрыв между положительными и отрицательными результатами решения задачи обфускации. Доказано, что для некоторых строго формализованных определений стойкости обфускации (стойкость в модели виртуального «чёрного ящика») существуют такие семейства эффективно вычислимых функций, которые не допускают стойкой обфускации [On the (im)possibility of obfuscating programs. 2001. P. 1–18; см. также On the (im)possibility of obfuscating programs. 2012. P. 1–48]. Стойкую обфускацию удалось построить для существенно более слабых требований стойкости и лишь для очень простых функций – точечных функций и близких к ним семейств функций (Canetti. 1997.^[10] P. 455–469; Varnovsky. 2003.^[11] P. 91–102; Lynn. 2004. P. 20–39; Wee. 2005. P. 523–532; Hofheinz. 2007.^[12] P. 214–232). Несмотря на то что положительные результаты были обобщены для более широких классов функций (Canetti. 2008. P. 489–508; Securely obfuscating re‐encryption. 2007.^[13] P. 233–252; Canetti.2010.^[14] P. 72–89), вопрос о возможности/невозможности эффективной обфускации для общих криптографических протоколов или же для любого значимого класса программ (например, для детерминированных автоматов) при стандартных криптографических предположениях остаётся открытым.

Проблема обфускации программ – очень сложная и многогранная задача, для неё вряд ли существует единый универсальный метод решения. Важнейшим направлением исследований этой проблемы является формирование математических основ для создания широкого многообразия формальных концепций и методов обфускации программ в контексте различных приложений. Создание такого математического аппарата требует разработки различных определений стойкости обфускации и исследования взаимосвязи между предложенными определениями и подходящими понятиями и моделями дискретной математики, математической криптографии, теории сложности вычислений. Наличие спектра различных определений стойкости обфускации позволяет понять, какие требования безопасности обеспечивают те или иные обфускирующие преобразования, и оценить, насколько эти преобразования удовлетворяют заявленным целям. Кроме того, введение новых формальных требований стойкости обфускации программ откроет новые возможности адаптации формальных методов теоретической информатики к решению задач защиты компьютерных программ.

↑ Diffie W. New directions in cryptography / W. Diffie, M. Hellman // IEEE Transactions on Information Theory. – 1976. – Vol. 22, № 6. – P. 644–654.
↑ Cohen F. B. Operating system protection through program evolution / Frederick B. Cohen // Computers and Security. – 1993 . – Vol. 12, № 6. – P. 565–584.
↑ Collberg C. Surreptitious software : obfuscation, watermarking, and tamperproofing for software protection / Christian Collberg, Jasvir Nagra. – Upper Saddle River, NJ : Addison‐Wesley, 2009. – (Software security).
↑ Information hiding : first international workshop Cambridge, U.K., May 30 - June 1, 1996 : proceedings / ed. by Ross Anderson. – Berlin : Springer, 1996. – (Lecture notes in computer science ; 1174).
↑ Hamilton J. An evaluation of the resilience of static java bytecode watermarks against distortive attacks / J. Hamilton, S. Danicic // International Journal of Computer Science. – 2011. – Vol. 38, № 1. – P. 1–15.
↑ Innovations and advanced techniques in computer and information sciences and engineering / ed. by Tarek Sobh. – Dordrecht : Springer, 2007.
↑ Jien-Tsai Chan. Advanced obfuscation techniques for Java bytecode / Jien-Tsai Chan, Wuu Yang // Journal of Systems and Software. – 2004. – Vol. 71, № 1–2. – P. 1–10.
↑ On the (im)possibility of obfuscating programs / Boaz Barak, Oded Goldreich, Russell Impagliazzo [et al.] // Journal of the ACM. – 2012. – Vol. 52, № 2. – P. 1–48.
↑ Varnovsky N. P. A note on the concept of obfuscation / N. P. Varnovsky // Proceedings of the Institute for System Programming. – 2004. – Vol. 6. – P. 127–136.
↑ Advances in Cryptology – CRYPTO'97 : 17th Annual International Cryptology Conference Santa Barbara, California, USA, August 17–21, 1997 : proceedings / ed. by B. S. Kaliski, Jr. – Berlin : Springer, 1997. – (Lecture notes in computer science ; 1294).
↑ Perspectives of system informatics : 5th International Andrei Ershov Memorial Conference, PSI 2003, Akademgorodok, Novosibirsk, Russia, July 9–12, 2003 : revised papers / ed. by M. Broy, A. V. Zamulin. – Berlin : Springer, 2003 . – (Lecture notes in computer science ; 2890).
↑ Theory of Cryptography : 4th Theory of Cryptography Conference, TCC 2007, Amsterdam, The Netherlands, February 21–24, 2007 : proceedings / ed. by Salil Vadhan. – Berlin : Springer, 2007. – (Lecture notes in computer science ; 4392).
↑ Theory of Cryptography : 4th Theory of Cryptography Conference, TCC 2007, Amsterdam, The Netherlands, February 21–24, 2007 : proceedings / ed. by Salil Vadhan. – Berlin : Springer, 2007. – (Lecture notes in computer science ; 4392).
↑ Theory of cryptography : 7th Theory of Cryptography Conference, TCC 2010, Zurich, Switzerland, February 9–11, 2010 : proceedings / ed. by Daniele Micciancio. – Berlin : Springer, 2010. – (Lecture notes in computer science ; 5978).

Diffie W. New directions in cryptography / W. Diffie, M. Hellman // IEEE Transactions on Information Theory. – 1976. – Vol. 22, № 6. – P. 644–654.
Cohen F. B. Operating system protection through program evolution // Computers and Security. – 1993. – Vol. 12, № 6. – P. 565–584.
Information hiding : first international workshop Cambridge, U.K., May 30 – June 1, 1996 : proceedings / ed. by R. Anderson. – Berlin : Springer, 1996.
Advances in Cryptology – CRYPTO'97 : 17th Annual International Cryptology Conference Santa Barbara, California, USA, August 17–21, 1997 : proceedings / ed. by B. S. Kaliski, Jr. – Berlin : Springer, 1997.
Chess D. An undetectable computer virus / D. Chess, S. White // Proceedings of the 2000 Virus Bulletin Conference. – 2000.
On the (im)possibility of obfuscating programs / B. Barak, O. Goldreich, R. Impagliazzo [et al.]
Ször P. Hunting for metamorphic / P. Ször, P. Ferrie // Proceedings of the 2001 Virus Bulletin Conference. – 2001. – P. 123–144.
Perspectives of system informatics : 5th International Andrei Ershov Memorial Conference, PSI 2003, Akademgorodok, Novosibirsk, Russia, July 9–12, 2003 : revised papers / ed. by M. Broy, A. V. Zamulin. – Berlin : Springer, 2003.
Varnovsky N. P. A note on the concept of obfuscation // Proceedings of the Institute for System Programming. – 2004. – Vol. 6. – P. 127–136.
Jien-Tsai Chan. Advanced obfuscation techniques for Java bytecode / Jien-Tsai Chan, Wuu Yang // Journal of Systems and Software. – 2004. – Vol. 71, № 1–2. – P. 1–10.
Lynn B. Positive results and techniques for obfuscation / B. Lynn, M. Prabhakaran, A. Sahai
Jun Ge. Control flow based obfuscation / Jun Ge, S. Chaudhuri, A. Tyagi // Proceedings of the 5th ACM Workshop on Digital Rights Management, Alexandria, VA, USA, November 7, 2005. – P. 83–92.
Wee H. On obfuscating point functions // Proceedings of the 37th annual ACM Symposium on Theory of Computing, May 2005. – 2005. – P. 523–532.
Innovations and advanced techniques in computer and information sciences and engineering / ed. by T. Sobh. – Dordrecht : Springer, 2007.
Goldwasser S. On best-possible obfuscation / S. Goldwasser, G. N. Rothblum
Theory of Cryptography : 4th Theory of Cryptography Conference, TCC 2007, Amsterdam, The Netherlands, February 21–24, 2007 : proceedings / ed. by S. Vadhan. – Berlin : Springer, 2007.
On the concept of software obfuscation in computer security / N. Kuzurin, A. Shokurov, N. Varnovsky, V. Zakharov
Theory of Cryptography : 4th Theory of Cryptography Conference, TCC 2007, Amsterdam, The Netherlands, February 21–24, 2007 : proceedings / ed. by S. Vadhan. – Berlin : Springer, 2007.
Canetti R. Obfuscating point functions with multibit output / R. Canetti, R. R. Dakdouk
Collberg C. Surreptitious software : obfuscation, watermarking, and tamperproofing for software protection / C. Collberg, J. Nagra. – Upper Saddle River, NJ : Addison‐Wesley, 2009. – (Software security).
Theory of cryptography : 7th Theory of Cryptography Conference, TCC 2010, Zurich, Switzerland, February 9–11, 2010 : proceedings / ed. by D. Micciancio. – Berlin : Springer, 2010.
Collberg C. Taxonomy of obfuscating transformations : technical report № 148 / C. Collberg, C. Thomborson, D. Low // The University of Auckland.
Hamilton J. An evaluation of the resilience of static java bytecode watermarks against distortive attacks / J. Hamilton, S. Danicic // International Journal of Computer Science. – 2011. – Vol. 38, № 1. – P. 1–15.
On the (im)possibility of obfuscating programs / B. Barak, O. Goldreich, R. Impagliazzo [et al.] // Journal of the ACM. – 2012. – Vol. 52, № 2. – P. 1–48.

[1] Diffie W. New directions in cryptography / W. Diffie, M. Hellman // IEEE Transactions on Information Theory. – 1976. – Vol. 22, № 6. – P. 644–654.

[2] Cohen F. B. Operating system protection through program evolution / Frederick B. Cohen // Computers and Security. – 1993 . – Vol. 12, № 6. – P. 565–584.

[3] Collberg C. Surreptitious software : obfuscation, watermarking, and tamperproofing for software protection / Christian Collberg, Jasvir Nagra. – Upper Saddle River, NJ : Addison‐Wesley, 2009. – (Software security).

[4] Information hiding : first international workshop Cambridge, U.K., May 30 - June 1, 1996 : proceedings / ed. by Ross Anderson. – Berlin : Springer, 1996. – (Lecture notes in computer science ; 1174).

[5] Hamilton J. An evaluation of the resilience of static java bytecode watermarks against distortive attacks / J. Hamilton, S. Danicic // International Journal of Computer Science. – 2011. – Vol. 38, № 1. – P. 1–15.

[6] Innovations and advanced techniques in computer and information sciences and engineering / ed. by Tarek Sobh. – Dordrecht : Springer, 2007.

[7] Jien-Tsai Chan. Advanced obfuscation techniques for Java bytecode / Jien-Tsai Chan, Wuu Yang // Journal of Systems and Software. – 2004. – Vol. 71, № 1–2. – P. 1–10.

[8] On the (im)possibility of obfuscating programs / Boaz Barak, Oded Goldreich, Russell Impagliazzo [et al.] // Journal of the ACM. – 2012. – Vol. 52, № 2. – P. 1–48.

[9] Varnovsky N. P. A note on the concept of obfuscation / N. P. Varnovsky // Proceedings of the Institute for System Programming. – 2004. – Vol. 6. – P. 127–136.

[10] Advances in Cryptology – CRYPTO'97 : 17th Annual International Cryptology Conference Santa Barbara, California, USA, August 17–21, 1997 : proceedings / ed. by B. S. Kaliski, Jr. – Berlin : Springer, 1997. – (Lecture notes in computer science ; 1294).

[11] Perspectives of system informatics : 5th International Andrei Ershov Memorial Conference, PSI 2003, Akademgorodok, Novosibirsk, Russia, July 9–12, 2003 : revised papers / ed. by M. Broy, A. V. Zamulin. – Berlin : Springer, 2003 . – (Lecture notes in computer science ; 2890).

[12] Theory of Cryptography : 4th Theory of Cryptography Conference, TCC 2007, Amsterdam, The Netherlands, February 21–24, 2007 : proceedings / ed. by Salil Vadhan. – Berlin : Springer, 2007. – (Lecture notes in computer science ; 4392).

[13] Theory of Cryptography : 4th Theory of Cryptography Conference, TCC 2007, Amsterdam, The Netherlands, February 21–24, 2007 : proceedings / ed. by Salil Vadhan. – Berlin : Springer, 2007. – (Lecture notes in computer science ; 4392).

[14] Theory of cryptography : 7th Theory of Cryptography Conference, TCC 2010, Zurich, Switzerland, February 9–11, 2010 : proceedings / ed. by Daniele Micciancio. – Berlin : Springer, 2010. – (Lecture notes in computer science ; 5978).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

Обфускация

Примечания

Литература