Исследование и разработка методологии маскировки программ тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Чернов, Александр Владимирович

• Чернов, Александр Владимирович
• кандидат физико-математических наук
• 2003

Оглавление диссертации кандидат физико-математических наук Чернов, Александр Владимирович

Введение

1 Маскирующие преобразования программ

1.1 Задача маскировки программ.

1.2 Используемая терминология.

1.3 Метрики сложности программ.

1.4 Расстояние между программами.

1.5 Определение устойчивости маскирующего преобразования

1.6 Методы анализа и трансформации программ.

1.7 Маскирующие преобразования программ.

1.7.1 Текстуальные маскирующие преобразования

1.7.2 Преобразования управляющей структуры.

1.7.3 Преобразования реструктуризации всей программы

1.7.4 Преобразования маскировки одной процедуры.

1.7.5 Непрозрачные предикаты.

1.7.6 Трансформация графа потока управления («диспетчер»).

1.7.7 Сравнение свойств разных маскирующих преобразований.

1.8 Использование маскирующих преобразований программ.

2 Анализ маскирующих преобразований программ

2.1 Анализ маскирующих преобразований.

2.1.1 Анализ лексических преобразований.

2.1.2 Анализ маскирующих преобразований графа потока управления

2.2 Классификация маскирующих преобразований программ.

2.3 Применение методов демаскировки.

2.3.1 Анализ замаскированных вручную программ.

2.3.2 Анализ программ, замаскированных автоматически.

2.4 Выводы.

3 Новый метод маскировки программ

3.1 Общее описание метода маскировки

3.1.1 Увеличение размера графа потока управления.

3.1.2 Разрушение структурности графа потока управления.

3.1.3 Генерация несущественного кода.

3.1.4 Перемешивание программ.

3.2 Реализация метода маскировки.

3.2.1 Увеличение графа потока управления процедуры.

3.2.2 Преобразования разрушения структурности.

3.2.3 Генерация несущественного кода.

3.2.4 «Зацепление» холостой и основной программы.

3.3 Устойчивость метода.

3.3.1 Формальная устойчивость метода.

3.3.2 Неформальная устойчивость метода.

3.4 Пример применения метода

3.5 Выводы.

4 Интегрированная среда Poirot

4.1 Архитектура системы.

4.2 Промежуточное представление.

4.3 Интерфейс пользователя.

4.3.1 Меню Analyze.

4.3.2 Меню Optimize.

4.3.3 Меню Transform.

4.3.4 Меню Obfuscate

4.3.5 Меню Generate.

4.3.6 Меню Execute.

4.3.7 Меню Visualize.

4.3.8 Меню Traces.

4.3.9 Меню Options.

Введение диссертации (часть автореферата) на тему «Исследование и разработка методологии маскировки программ»

В настоящее время особенную актуальность приобрели задачи, связанные с защитой информации. Компьютерные программы как один из видов информации также нуждаются в защите. Проблематика защиты программ включает в себя как защиту от копирования и (или) нелицензионного использования, так и защиту от обратной инженерии и несанкционированной модификации.

В диссертации рассматривается проблема защиты программ от обратной инженерии, проводимой с целью модификации и/или включения фрагментов защищаемой программы во вновь разрабатываемый программный код. Защита в данном случае состоит в том, чтобы затруднить понимание деталей реализации компонент большой программной системы, сделав его настолько дорогим, чтобы дешевле было разработать оригинальное программное обеспечение. Одним из способов такой защиты является маскировка программ, заключающаяся в применении к исходному тексту программы цепочки маскирующих преобразований, то есть преобразований, сохраняющих реализуемую программой функцию (являющихся функционально эквивалентными), но затрудняющих понимание этой функции.

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

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

Напрашивается и введение качественной характеристики самого метода маскировки. Подходящей, на наш взгляд, может быть характеристика, построенная на следующих соображениях. Замаскированная программа подвергается атаке демаскирующих преобразований, являющихся тоже функционально эквивалентными и стремящихся восстановить исходный вид программы. Отбросим как маловероятные демаскирующие преобразования, основанные на анализе программ, проводимом вручную. Тогда остаются оптимизационные преобразования, опирающиеся на алгоритмы автоматического анализа программ. Ограничившись некоторым набором таких оптимизационных преобразований и используемых ими алгоритмов анализа программ, можно говорить об устойчивости метода маскировки по отношению к данному набору демаскирующих преобразований. Для этого вводится понятие расстояния между функционально эквивалентными программами, и требуется, чтобы расстояние между исходной программой и программой, полученной действием произвольной цепочки оптимизационных преобразований из фиксированного набора на замаскированную программу, было не меньше заданной пороговой величины, называемой порогом устойчивости.

Цель исследования. Основной задачей диссертационной работы является разработка нового метода маскировки программ, удовлетворяющего следующим требованиям:

1. Исходная и замаскированная программа записаны на языке Си [8].

2. В методе применяются цепочки маскирующих преобразований, элементы которых берутся из некоторого заранее зафиксированного множества параметризированных маскирующих преобразований.

3. Все цепочки таких преобразований порождаются автоматически поддерживающими метод инструментальными средствами и являются допустимыми по своим характеристикам.

4. Метод маскировки устойчив относительно современных методов статического и полустатического анализа программ, развитых для языка Си.

Необходимым условием достижения цели исследования является разработка подходящей инструментальной системы и глубокий анализ применяемых на практике методов маскировки программ. Такой анализ должен выявить практически разумные величины всех ограничений, а именно: на границы допустимых увеличений характеристик маскируемой программы, на сложность реализации демаскирующих преобразований и на порог устойчивости.

Актуальность темы. Необходимость разработки средств защиты программ от обратной инженерии подтверждается следующими наблюдениями. Во-первых, для обеспечения переносимости программ на разные платформы в ряде случаев они распространяются в исходных кодах на языке высокого уровня. Например, система статического анализа программ на Си и Си++[15] FlexeLint [42] распространяется в замаскированных исходных файлах. Во-вторых, широко распространены языки программирования, такие как Java [2], в которых «исполняемой» формой программы является не машинный код для некоторого типа процессоров, а машинно-нейтральное представление. Задача декомпиляции программы из такого представления обратно в программу на языке Java значительно проще, чем декомпиляция из машинного кода, и успешно решена [71].

Основные результаты работы. В диссертации получены следующие основные результаты:

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

2. Установлена степень устойчивости опубликованных методов маскировки программ по отношению к фиксированному набору современных методов статического и полустатического анализа программ и основанных на них демаскирующих преобразований. На этом основании предложена классификация методов маскировки.

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

4. Разработана и реализована прототипная версия инструментальной среды Poirot, обеспечивающей возможность маскировки и демаскировки программ, а также поддерживающей анализ маскирующих преобразований программ и разработку новых маскирующих преобразований.

Интегрированная среда Poirot, являясь расширяемой, позволяет добавлять новые методы анализа и трансформации программ. Прототипная версия среды Poirot носит предварительный характер и является базовым средством, обеспечившим проведение исследований.

Научная новизна работы. Все полученные в диссертационной работе результаты являются новыми.

Практическая ценность работы. Система Poirot позволяет демаскировать замаскированные программы и маскировать программы устойчивым образом. Она помещена в открытый доступ в Internet и может использоваться для анализа существующих методов маскировки программ и разработки новых методов маскировки программ, непосредственно для маскировки программ и анализа замаскированных программ, а также для решения некоторых проблем обратной инженерии. С помощью интегрированной среды Poirot исследованы методы маскировки программ, используемые одним из коммерческих маскировщиков, и выявлены слабые стороны этого метода. Интегрированная среда используется в учебном процессе на факультетах ВМиК МГУ и ФПМЭ МФТИ.

С помощью интегрированной среды Poirot разработан новый метод автоматического разбиения последовательной программы на нити, который учитывает локальность доступов к данным [29].

Апробация работы. Основные результаты работы опубликованы в работах [16, 17, 18, 19, 28]. Результаты работы обсуждались на следующих конференциях и семинарах:

• Научно-исследовательском семинаре по автоматизации программирования под руководством проф. М. Р. Шуры-Буры.

• Конференции, посвященной 90-летию со дня рождения А. А. Ляпунова, Россия, Новосибирск, 8—11 октября 2001 года.

• Школе-семинаре молодых учёных факультета ВМиК МГУ, Дубна, октябрь 2001.

• Тихоновских чтениях факультета ВМиК МГУ, 30 октября 2002 года.

• Семинаре "International Workshop on Program Understanding" в рамках Пятой международная конференции «Перспективы систем информатики», 9—12 июля 2003 г., Россия, Новосибирск.

Объём и структура диссертации. Работа состоит из введения, четырёх глав, заключения и списка литературы. Общий объём диссертации — 133 страницы, в том числе 49 иллюстраций и 9 таблиц. Список литературы содержит 81 наименование.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Чернов, Александр Владимирович

Результаты работы могут использоваться для маскировки и демаскировки программ на языке Си.

Заключение

В работе впервые было проведено систематическое исследование опубликованных маскирующих преобразований и методов маскировки программ с точки зрения их устойчивости против современных алгоритмов статического и полустатического анализа программ. В работе показано, что применение ранее опубликованных методов не позволяет маскировать программы устойчивым по отношению к некоторому набору алгоритмов анализа программ образом. Автором разработан новый метод маскировки программ, свободный от выявленных недостатков и устойчивый к данному набору алгоритмов анализа программ.

В диссертации получены следующие основные результаты:

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

2. Установлена степень устойчивости опубликованных методов маскировки программ по отношению к фиксированному набору современных методов статического и полустатического анализа программ и основанных на них демаскирующих преобразований. На этом основании предложена классификация методов маскировки.

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

4. Разработана и реализована прототипная версия инструментальной среды Poirot, обеспечивающей возможность маскировки и демаскировки программ, а также поддерживающей анализ маскирующих преобразований программ и разработку новых маскирующих преобразований.

Дальнейшие исследования по результатам диссертации будут вестись в следующих направлениях:

1. разработка новых методов демаскировки замаскированных программ;

2. применение подхода, развитого в настоящей работе, к маскировке и оценке устойчивости замаскированных программ большого размера;

3. дальнейшее развитие интегрированной среды Poirot.

Список литературы диссертационного исследования кандидат физико-математических наук Чернов, Александр Владимирович, 2003 год

1. В. Н. Агафонов. Спецификация программ: понятийные средства и их организация. М.: «Наука», 1987.

2. К. Арнольд, Д. Гослинг, Д. Холмс. Язык программирования Java. Пер. с англ. М.: Вильяме, 2001.

3. А. Ахо, Р. Сети, Д. Улльман. Компиляторы. Принципы, технологии, инструменты. Пер. с англ. М.: Вильяме, 2001.

4. А. Ахо, Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов. Пер. с англ. М.: Мир, 1979.

5. Введение в криптографию. Под общей редакцией В. В. Ященко. М.: МЦМНО, 1999.

6. М. Гери, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. Пер. с англ. М.: Мир, 1982.

7. Р. Грэхем, Д. Кнут, О. Паташник. Конкретная математика. Основания информатики. Пер. с англ. М.: Мир, 1998.

8. Б. В. Керниган, Д. М. Ритчи. Язык программирования Си. Пер. с англ. СПб.: Невский диалект, 2001.

9. Д. Э. Кнут. Искусство программирования. Том 2. Получисленные алгоритмы. Пер. с англ. М.: Вильяме, 1998.

10. Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ. Пер. с англ. М.: МЦНМО, 2000.

11. В. В. Липаев. Качество программного обеспечения. М.: Финансы и статистика, 1983.

12. В. В. Липаев. Тестирование программ. М.: Радио и связь, 1986.

13. Д. Пик, Т. О'Райли, М. Лукидис. Unix. Инструментальные средства. Пер. с англ. М.: BHV, 2002.

14. Р. И. Подловченко. Эквивалентные преобразования схем программ для "запутывания" самих программ//Программирование. — 2002 — №2 — С. 66-80.

15. Б. Страуструп. Язык программирования С++. Пер. с англ. М.: Бином, 1999.

16. А. В. Чернов. Интегрированная среда для исследования «обфускации» программ. Доклад на конференции, посвященной 90-летию со дня рождения А. А. Ляпунова. Россия, Новосибирск, 8—11 октября 2001 года.http://www-sbras.nsc.ru/ws/showabstract.dhtml?ru+19+2350

17. А. В. Чернов. Анализ запутывающих преобразований программ//В сб. «Труды Института системного программирования РАН», под ред. В. П. Иванникова. М.: ИСП РАН, 2002.

18. А. В. Чернов. Об одном методе маскировки программ//В сб. «Труды Института системного программирования РАН», под ред. В. П. Иванникова. М.: ИСП РАН, 2003.

19. А. В. Чернов. Интегрированная инструментальная среда Poirot для изучения методов маскировки программ. Препринт Института системного программирования РАН. М.: ИСП РАН, 2003.

20. С. В. Яблонский. Введение в дискретную математику. М.: Наука, 1986.

21. A. W. Appel. Modern Compiler Implementation in С. Cambridge University Press. 1998.

22. M. Arnold, S. Fink, D. Grove, M. Hind, P. F. Sweeney. Adaptive Optimizations in the Jalapeno JVM. In Proceedings of ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA'OO), 2000.

23. T. Ball, J. R. Larus. Optimally Profiling and Tracing Programs. In Proceedings of the Nineteenth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'92), 1992.

24. T. Ball, J. R. Larus. Efficient Path Profiling. In Proceedings of the 29th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-29), 1996.

25. B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. Vadhan, K. Yang. On the (Im)possibility of Obfuscating Programs. LNCS 2139, pp. 1-18, 2001.

26. B. Calder, P. Feller, A. Eustace. Value Profiling. In Proceedings of the 30th International Symposium on Microarchitecture (MICROSO), 1997.

27. P. P. Chang, S. A. Mahlke, W. W. Hwu. Using Profile Information to Assist Classic Code Optimizations. In Software Practice and Experience, 21(12): 1301-1321, December 1991.

28. A. Chernov. A New Program Obfuscation Method. In Proceedings of the Adrei Ershov Fifth International Conference "Perspectives of Systems Informatics". International Workshop on Program Understanding, Novosibirsk, July 14-16, 2003.

29. S. Chow, Y. Gu, H. Johnson, V. Zakharov. An approach to the obfuscation of control-flow of sequential computer programs. LNCS 2200, pp. 144-155, 2001.

30. С. Cifuentes, К. J. Gough. Decompilation of Binary Programs. Technical report FIT-TR-1994-03. Queensland University of Technology, 1994.http://www.fit.qut.edu.au/TR/techreports/FIT-TR-94-03.ps

31. Cloakware Corp. Web Page, http://www.cloakware.com

32. C. Collberg, C. Thomborson, D. Low. A Taxonomy of Obfuscating Transformations. Departament of Computer Science, The University of Aukland, 1997.http://www.cs.arizona.edu/~collberg/Research/Publications/ ** CollbergThomborsonLow97a

33. C. Collberg, C. Thomborson, D. Low. Breaking Abstractions and Unstructuring Data Structures. In Proceedings of the IEEE International Conference on Computer Languages (ICCL'98), Chicago, IL, May 1998.

34. C. Collberg, C. Thomborson, D. Low. Manufacturing Cheap, Resilient, and Stealthy Opaque Constructs. In Proceedings of the International Conference on Principles of Programming Languages (POPL'98), San Diego, CA, Januaiy 1998.

35. C. Collberg, C. Thomborson. On the Limits of Software Watermarking. Technical Report #164. Departament of Computer Science, The University of Aukland, 1998.http://www.cs.arizona.edu/~соliberg/Research/Publications/«• CollbergThomborson98e

36. R. Cytron, J. Ferrante, В. K. Rosen, M. N. Wegman, F. K. Zadeck. Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems, 13(4): 450-90, October 1991.

37. R. Cytron, R. Gershbein. Efficient Accommodation of May-Alias Information in SSA Form, in Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'93), pp. 36-45, June 1993.

38. DashO-Pro. Java Code Optimizer, Obfuscator, Compressor.http://www.codework.com/dashO/product.html41. The dcc decompiler.http://www.itее.uq.edu.au/~cristina/dcc.html

39. Gimpel Software Home Page for PC-lint and FlexeLint for C/C++.http://www.gimpel.com/

40. Google Web Directory. Decompilers and Disassemblers.http://directory.google.com/Top/Computers/Programming/Languages/«• Java/DevelopmentTools/Translators/DecompilersandDisassemblers/

41. Google Web Directory. Obfuscators.http://directory.google. com/Top/Computers/Programming/Languages/** Java/DevelopmentTooIs/Obfuscators/

42. R. Gupta, D. Berson, J. Z. Fang. Path Profile Guided Partial Redundancy Elimination Using Speculation. In Proceedings of the IEEE International Conference on Computer Languages (ICCL'98), pp. 230-239, 1998.

43. Y. Gurevich. Evolving Algebras. In Proceedings of the IFIP 13th World Computer Congress, volume I: Technology/Foundations, pp. 423-427, 1994.

44. G. Hachez, C. Vasserot. State of the Art in Software Protection. Project FILIGRANE (Flexible IPR for Software Agent Reliance) deliverabIe/V2.http://www. dice.ucl.ac.be/crypto/filigrane/External/d21.pdf

45. W. H. Harrison. Compiler Analysis of the Value Ranges for Variables. In IEEE Transactions on Software Engineering, 3(3): 243-250, May 1977.

46. W. A. Harrison, К. I. Magel. A complexity measure based on nesting level. In SIGPLAN notices, 16(3):63—74, 1981.

47. M. H. Halstead. Elements of Software Science. Elsevier North-Holland, 1977.

48. S. Henry, D. Kafura. Software structure metrics based on information flow. IEEE Transactions on Software Engineering, 7(5): 510-518, September 1981.

49. M. Hind, A. Pioli. Which pointer analysis should I use? In Proceedings of the ACM SIGSOFT International Symposium on Software Testing and Analysis, pp. 113-123, August 2000

50. S. Horwitz. Precise Flow-Insensitive May-Alias Analysis Is NP-Hard. In ACM Transactions on Programming Languages and Systems, 19(1): 1-6, January 1997.

51. Introduction to HOL. A theorem proving environment for higher order logic. Edited by M. J. C. Gordon and T. F. Melham. Cambridge University Press, 1993.

52. The International Obfuscated С Code Contest, http://www.ioccc.org

53. H. Lai. A comparative survey of Java obfuscators available on the internet.http://www.cs . auckland.ac.nz/~cthombor/Students/hlai

54. M. H. Lipasti, С. B. Wilkerson, J. P. Shen. Value Locality and Load Value Prediction. In Proceedings of the Seventh International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-VII), 1996.

55. D. Low. Java Control Flow Obfuscation. MSc Thesis. University of Aukland, 1998. http://www.cs.arizona.edu/~collberg/Research/Student s/** DouglasLow/thesis.ps

56. J. MacDonald. On Program Security and Obfuscation. 1998. http://www.xcf.berkeley.edu/~jmacd/cs261.pdf

57. M. Mambo, T. Murayama, E. Okamoto. A Tentative Approach to Constructing Tamper-Resistant Software. In Proceedings of the ACM New Security Paradigms Workshop, Langdale, Cumbria UK, 1998.

58. A. von Mayrhauser, A. M. Vans. Program Understanding: Models and Experiments. In M. Yovits, M. Zelkowitz (eds.), Advances in Computers, Vol 40, 1995. San Diego: Academic Press, pp. 1-38.

59. S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, 1997.

60. H. A. Muller Understanding Software Systems Using Reverse Engineering Technologies Research and Practice. In Proceedings of the 18th International Conference on Software Engineering (1CSE-18), 1996.

61. R. Muth, S. Watterson, S. Debray. Code Specialization based on Value Profiles. In Proceedings of the 7th International Static Analysis Symposium (SAS'2000), 2000. LNCS 1824, pp. 340-359.

62. J. Q. Ning, A. Engberts, W. Kozaczynski. Automated Support for Legacy Code Understanding. In Communications of the ACM, 37(5): 50-57, May 1994.

63. E. I. Oviedo. Control flow, data flow, and program complexity. In Proceedings of IEEE COMPSAC, 1980, pp. 146-152.

64. The Poirot IRE download page, http://www.ispras.ru/groups/ctt/ire.html

65. G. Ramalingam. The Undecidability of Aliasing. In ACM Transactions on Programming Languages and Systems, 16(5): 1467-1471, 1994.

66. SourceAgain Java decompiler.http://www.ahpah.com

67. B. Schneier. Applied Cryptography: protocols, algorithms and source code in C. Second Edition. John Wiley & Sons, Inc., 1996.

68. M. Spivey. Fast, accurate call graph profiling. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'02), 2002.

69. B. Steensgaard. Points-to analysis by type inference of programs with structures and unions. In Proceedings of the 6th International Conference on Compiler Construction. LNCS 1060, pp. 136-150, 1996.

70. F. Tip. A survey of program slicing techniques. Journal of Programming Languages, 3(3): 121—189, September 1995.

71. N. P. Varnovsky, V. A. Zakharov. On the Possibility of Provably Secure Obfuscating Programs. In Perspectives of System Informatics (Proceedings of Andrei Ershov Fifth International Conference), Novosibirsk, July 2003.

72. E. Walle. Methodology and Applications of Program Code Obfuscation. Faculty of Computer and Electrical Engineering, University of Waterloo, 2001.http://walle. dyndns.org/morass/misc/wtr3b.doc

73. C. Wang. A Security Architecture for Survivability Mechanisms. PhD Thesis. Departament of Computer Science, University of Virginia, 2000.http://www.cs.Virginia.edu/~survive/pub/wangthesis.pdf

74. C. Wang, J. Davidson, J. Hill, J. Knight. Protection of Software-based Survivability Mechanisms. Departament of Computer Science, University of Virginia, 2001.http://www.es.virginia.edu/~jck/publications/*' dsndistribute.pdf

75. G. Wroblewski. General Method of Program Code Obfuscation. PhD Thesis. Wroclaw, 2002.

76. Zelix KlassMaster Java Code Obfuscator and Obfuscation. http://www.zelix.com