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

В качестве примера применения предложенного метода маскировки мы выбрали небольшую программу, которая решает задачу о 8 ферзях. Текст этой программы приведён на рис. 10.

Рис. 10. Программа, решающая задачу о "8 ферзях"

Для маскировки мы выберем основную функцию queens этой программы. Граф потока управления функции queens приведён на рис. 11.

Рис. 11. Граф потока управления функции queens

Результат маскировки функции queens приведён ниже.

static void queens(int c)
{
  int q[13u];
  q[10] = 0;
  q[8] = 0;
  q[1] = (c + 7);
  q[4] = 0;
  q[7] = 0;
  q[2] = -1;
  q[11] = 0;
 L127:  if (!q[2]) goto L128;
  q[11]++;
  q[2] = (unsigned) q[2] >> 1;
  goto L127;
 L128:  q[12] = q[11]+q[2]-19;
  q[11] = q[11] % q[12];
  L111: 
  if (q[q[11]+4] >= 8) goto L45;
  q[3] = q[10];
  q[q[11]+2] = ((q[8] + q[7]) + 1);
  q[9] = (q[10] + 1);
  q[1] = ((q[1] + c) + 2);
  q[q[11]+4] = (q[10] + 2);
  q[7] = ((7 + q[q[11]+2]) - q[1]);
  if ((v3)[q[3]] == 0) goto L94;
  q[4] = ((v8)[q[3]] + (v2)[((q[3] - c) + 7)]);
  if ((v7)[((q[3] - c) + 7)] == 0) goto L94;
  if (q[7] < 0) goto L96;
  if (q[7] <= 7) goto L97;
  L96: 
  q[7] = ((q[3] - c) + 7);
  L97:  if ((v4)[(q[3] + c)] == 0) goto L94;
  q[1] = (q[8] + (v2)[q[7]]);
  q[2] = (((c * (c + 1)) * q[3]) % 4);
  goto L99;
  L122:  if (q[5] <= 0) goto L101;
  (v4)[(q[3] + c)] = 0;
  (v2)[((q[3] - c) + 7)] = 0;
  (v7)[((q[3] - c) + 7)] = 0;
  (v3)[q[3]] = 0;
  (v5)[c] = q[3];
  (v8)[c] = q[q[11]+2];
  q[5] = ((q[5] + 1) != 2);
  goto L102;
  L101:  q[7] = (q[7] + 2);
  if (q[7] <= 14) goto L103;
  q[7] = (q[3] + c);
  L103:  q[4] = (v2)[q[7]];
  (v4)[(q[3] + c)] = 0;
  q[1] = 0;
  (v7)[((q[3] - c) + 7)] = 0;
  (v8)[q[3]] = q[1];
  (v3)[q[3]] = 0;
  (v5)[c] = q[3];
  q[5] = ((q[5] + 4) != 5);
  q[1] = (v8)[c];
  L102:  if (c != 7) goto L105;
  L104:  print();
  q[4] = ((c * 5) + 4);
  q[q[11]+2] = (v8)[c];
  (v8)[c] = q[4];
  goto L106;
  L105:  q[q[11]] = ((c * 5) + 3);
  (v2)[((q[3] - c) + 7)] = ((q[8] + q[1]) - 7);
  L115: 
  if ((q[6] % 5) < 2) goto L108;
  q[4] = ((q[q[11]] % 5) + c);
  if ((q[4] % 7) != 0) goto L109;
  q[4] = 1;
  L109:  q[1] = ((q[4] * q[4]) % 7);
  q[1] = ((q[1] * q[1]) * q[1]);
  c = ((c + (q[1] % 7)) - 1);
  queens(((c + 1)));
  q[11] = (q[q[11]+5] + q[12]) % 13;
  L106:  (v4)[(q[3] + c)] = 1;
  (v2)[(q[3] + c)] = q[q[11]+2];
  (v7)[((q[3] - c) + 7)] = 1;
  (v8)[q[3]] = 1;
  (v3)[q[3]] = 1;
  q[4] = (((v2)[(q[3] + c)] + c) + 7);
  L94:  q[1] = (q[4] > 5);
  if ((v3)[q[9]] == 0) goto L111;
  if ((v7)[((q[9] - c) + 7)] != 0) goto L112;
  if (q[1] != 0) goto L111;
  if (q[4] <= 5) goto L111;
  L112:  if ((v4)[(q[9] + c)] == 0) goto L111;
  q[6] = (((q[9] + c) * 5) + 1);
  q[1] = ((q[q[11]] + q[8]) + 1);
  goto L115;
  L108:  (v2)[((q[9] - c) + 7)] = q[5];
  (v4)[(q[9] + c)] = 0;
  (v8)[q[9]] = (v3)[q[9]];
  (v7)[((q[9] - c) + 7)] = 0;
  q[7] = (q[9] + c);
  (v3)[q[9]] = 0;
  q[8] = ((q[5] + q[2]) + 7);
  (v5)[c] = q[9];
  (v8)[c] = q[q[11]+2];
  if (c != 7) goto L117;
  L116: print();
  q[1] = (v8)[c];
  (v8)[c] = q[4];
  goto L118;
  L117:  (v8)[(c + 1)] = q[1];
  queens(((c + 1)));
  L118:  q[8] = ((v2)[(q[9] + c)] + q[1]);
  q[1] = ((q[8] + q[7]) + q[5]);
  if (((v1)[((((q[9] - c) + 7) ^ q[5]) % 4)] % 4) != 1) goto L120;
  (v2)[((q[9] - c) + 7)] = ((q[7] + q[9]) - c);
  (v4)[(q[9] + c)] = 1;
  q[4] = (q[q[11]+2] + 1);
  (v8)[q[9]] = 1;
  (v7)[((q[9] - c) + 7)] = 1;
  (v3)[q[9]] = 1;
  q[11] = (q[11] + q[q[11]+6]) % 13;
  goto L111;
  L120:  q[2] = ((((v7)[(q[9] - c)] + 7) | 1211) % 6);
  q[4] = (q[8] + ((v7)[(q[9] - c)] | 1211));
  q[7] = (q[7] + 1);
  L99:  if ((v6)[q[2]] > (v6)[(q[2] + 1)]) goto L122;
  (v2)[(q[9] + c)] = ((v6)[q[2]] + c);
  q[8] = (((q[1] + q[4]) + q[9]) - 7);
  (v4)[(q[9] + c)] = 1;
  q[4] = (v8)[q[9]];
  (v8)[q[9]] = 1;
  (v7)[((q[9] - c) + 7)] = 1;
  q[7] = (q[7] - 1);
  (v3)[q[9]] = 1;
  q[q[11]+5] = (q[11] + q[12]) % 13;
  goto L111;
  L45: ;
}

Граф потока управления замаскированной функции приведён на рис. 12. На рисунке графа дуги, получившиеся при выполнении преобразования зацепления дуг, имеют большую толщину, а соответствующие базовые блоки выделены серым цветом.

Рис. 12. Граф потока управления замаскированной функции queens

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

1. Массив q используется для хранения локальных переменных функции queens. В результате методы анализа потока данных, которые не различают индивидуальные элементы массива, покажут зависимости по данным между всеми операциями с массивом q, то есть между всеми локальными переменными функции queens.
2. Для противодействия алгоритмам анализа потока данных, различающим элементы массива, для доступа к массиву q используется переменная, отображённая в элемент q[11] массива. Переменная инициализируется значением 6 в строках 9-18 функции. Для этого используется константа 32, получаемая в цикле как количество бит в целом слове, и константа 13 - количество элементов в массиве локальных переменных, которое сохраняется в элементе q[12] для последующего использования. Для анализа программы необходимо установить, что элементы q[11] и q[12] являются константами, что в данном случае возможно для методов, различающих элементы массива, но вычисление этих констант потребует интерпретации программы.
3. Для противодействия алгоритмам продвижения констант, которые могли бы распространить константные значения q[11] и q[12] по функции, значение q[11] перевычисляется в строках 82, 129, 145. При этом значение q[11] каждый раз не изменяется.
4. В случае, даже если в результате анализа замаскированной функции удалось выделить каждый элемент массива в отдельную переменную, замаскированная функция всё ещё содержит весь несущественный код, внесённый при маскировке. Алгоритм обнаружения мёртвого кода не даст результатов, из-за использования тождеств в строках 70-79 и 91-96, вносящих ложные зависимости по данным между основной и несущественной частью функции queens.

   Таблица 1. Изменение метрик сложности для замаскированной функции queens
   метрика	исходная функция	после преобразования
   CC (Цикломатическая сложность) [14]	6	21
   FC (Сложность по связям) [13]	9	27
   GC (Сложность графа вызовов)	2	2
   SC (Структурная сложность) [13]	3	24
   YC (Зацикленность)	0.595	0.8119
   DC (Сложность потока данных)	82	8964

   
   

5. Кроме того, дополнительные зависимости по данным и дополнительные дуги графа потока управления появляются из-за использования зацепления дуг. Первое зацепление реализовано в строках 36-38 и 131-136, а второе зацепление - в строках 70-73 и 98-100.

Заключение

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

1. Метод существенно увеличивает сложность графа потока управления маскируемых функций за счёт клонирования и расщепления базовых блоков, а также добавления дуг, разрушающих его структурность.
2. Метод существенно увеличивает сложность графа зависимостей по данным маскируемых функций за счёт внесения в тело функции несущественного кода. Основной код функции и введённый несущественный код зависят друг от друга по данным за счёт использования тождеств и указателей.
3. Метод устойчив к известным методам статического анализа программ, так как, в частности, вносит в маскируемую функцию динамические структуры данных.
4. Метод более устойчив к полустатическим методам анализа, чем другие известные методы маскировки функций, так как замаскированная функция не содержит "мёртвых" дуг в графе потока управления.

Список литературы

1. К. Арнольд, Д. Гослинг, Д. Холмс. Язык программирования Java. М.: Вильямс, 2001.
2. Введение в криптографию. Под общей редакцией В. В. Ященко. М.: МЦМНО, 1999.
3. Р. Грэхем, Д. Кнут, О. Паташник. Конкретная математика. Основания информатики. М.: Мир, 1998.
4. Б. В. Керниган, Д. М. Ритчи. Язык программирования Си. СПб.: Невский диалект, 2001.
5. Д. Э. Кнут. Искусство программирования. Том 2. Получисленные алгоритмы. М.: Вильямс, 1998.
6. Б. Страуструп. Язык программирования C++. М.: Бином, 1999.
7. В. Чернов. Интегрированная среда для исследования "обфускации" программ. Доклад на конференции, посвящённой 90-летию со дня рождения А. А. Ляпунова. Россия, Новосибирск, 8-11 октября 2001 года.
8. А. В. Чернов. Анализ запутывающих преобразований программ//В сб. "Труды Института системного программирования", под. ред. В. П. Иванникова. М.: ИСП РАН, 2002.
9. 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.
10. 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.
11. C. Collberg, C. Thomborson, D. Low. A Taxonomy of Obfuscating Transformations. Departament of Computer Science, The University of Aukland, 1997.
12. C. Collberg, C. Thomborson, D. Low. Breaking Abstractions and Unstructuring Data Structures. In Proc. of the IEEE Internat. Conf. on Computer Languages (ICCL'98), Chicago, IL, May 1998.
13. W. A. Harrison, K. I. Magel. A complexity measure based on nesting level. In SIGPLAN notices, 16(3):63-74, 1981.
14. M. H. Halstead. Elements of Software Science. Elsevier North-Holland, 1977.
15. S. Henry, D. Kafura. Software structure metrics based on information flow. IEEE Transactions on Software Engineering, 7(5): 510--518, September 1981.
16. S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, 1997.
17. B. Schneier. Applied Cryptography: protocols, algorithms and source code in C. Second Edition. John Wiley & Sons, Inc., 1996.
18. 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
19. G. Wroblewski. General Method of Program Code Obfuscation. PhD Thesis. Wroclaw, 2002.