среда, 29 апреля 2009 г.

Переменные цвета хаки

1. Введение в проблему


Разрабатывая очередное приложение/игру, задумываетесь ли вы о приватности ваших переменных? Что если переменные, которые служили вам верой и правдой в процессе отладки и тестирования, начнут вдруг ни с того ни с сего менять свои значения прямо на этапе выполнения? Сами по себе они вряд ли станут это делать. Кому-то это должно быть выгодно. В играх, например, всегда присутствует некий критерий продвинутости игрока (очки, баллы, монетки, время и т.д.). Всегда найдутся желающие "накрутить" себе баллов.

2. Какие у нас варианты?


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

Во-вторых, существуют методы по шифрованию данных, хранимых в переменных. Если в шифровании нет проверки на валидность, то методом проб и ошибок всё равно подбирается желанное число очков. Если проверка на валидность данных присутствует, то очки на глаз уже не заполучить. А вот заморозить шифрованную переменную можно. А если это жизни игрока? Нехорошо получается . . .

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

3. "Беспалевно" меняем значение


Например, будем прятать от читеров целые числа. Создадим класс, в последующем он заменит нам тип int. Будем хранить необходимое значение в двух или трёх переменных. Их сумма и будет "значением". При изменении значения мы будем менять лишь одну из переменных. Изменяемую переменную выберем случайным образом.

// код не проверен, написан с телефона
class int_3
{
    int vect[3];
public:
    int_3(int value = 0) {
      operator = (value);
    }

    // Сумма всех элементов,
    // кроме указанного
    int sum(int exclude = -1) {
      int s = 0;
      for (int i=0; i<3; i++)
         if (i != exclude)
             s += vect[i];
      return s;
    }

    operator int() {
      return sum();
    }
    int operator = (int value) {
      int index = rand() % 3;
      vect[index] = value - sum(index);
      return value;
    }
    int operator + (int value) {
      return operator = (sum() + value);
    }
    int operator - (int value) {
      return operator = (sum() - value);
    }
    int operator * (int value) {
      return operator = (sum() * value);
    }
    int operator / (int value) {
      return operator = (sum() / value);
    }
    // ...
};


* This source code was highlighted with Source Code Highlighter.


При выполнении любой из операции изменяется значение ровно одной ячейки памяти. Но это ещё не всё: тот, кто знает наш способ, может придумать, как нас всё-таки обмануть.

- Например, при изменении значения, всегда меняется значение 12-ти байтового числа (смежные поля класса лежат рядом в памяти). Изменения 12-ти символьной строки можно отловить . . .

- Можно хранить три частичных значения в динамической памяти. Тогда у нас будет массив из указателей. Сам массиив не изменяется, изменяются ячейки памяти, которые располагаются отнюдь не рядом. При желании можно "специально" между выделениями памяти под наши переменные выделять память под относительно большие массивы, а потом просто её высвобождать, чтоб уж точно переменные лежали в разных местах.


- Масштабируемость алгоритма налицо - можно завести вектор подлиннее, а ещё лучше сделать длину динамической. Ну и, конечно же, оформить не классом, а шаблоном.

P.S.
Главное не обращать внимания на переполнение разрядности чисел при сложении и вычитании. Не верите? Вот Вам пример:
a,b,c - элементы вектора (0..9)
x - загружаемое значение
Будем считать что генератор случайных чисел выдаёт следующую последовательность:
0 1 2 0 1 2 0 1 2 . . .
a b c x
0 0 0 5
5 0 0 8
5 3 0 2
5 3 4 5
8 3 4 1
8 9 4 0
8 9 3 0
8 9 3 0
8 9 3 0
. . . .

4. Реализация всех выдуманных примочек


В результате у меня получился вот такой вот шаблончик:
// Copyright by [k06a] © 2009

#include <iostream>

using namespace std;

template<class T> class int_x
{
  T **vect;
  int size;

public:
  // Конструкторы
  int_x( int value_ = 0, int size_ = 2, int scrambler = 0 ) {
     init( value_, size_, scrambler );
  }
  int_x( int_x & var ) {
     init( var.sum(), var.size );
  }
  // Для работы: int_x<int> var = 5;
  int_x( int_x const & var ) {
     init( var.sum(), var.size );
  }
  ~int_x() {
     deinit();
  }

  int_x & operator = (int_x var) {
     deinit();
     init( var.sum(), var.size );
  }

  // [Де]Инициализация
  void init(int value_ = 0, int size_ = 2, int scrambler = 0)
  {
     size = size_;
     vect = new T* [size_];
     char *buf = NULL;

     for (int i=0; i<size; i++)
     {
         if (scrambler)
            buf = new char [rand()%scrambler];
         vect[i] = new T;
         if (scrambler)
            delete [] buf;
     }
     operator = (value_);
  }
  void deinit()
  {
     for (int i=0; i<size; i++)
         delete vect[i];
     delete [] vect;
     vect = NULL;
  }

  // Сумма всех эллементов, кроме указанного
  T sum(int exclude = -1) const
  {
     T summa = 0;
     for (int i=0; i<size; i++)
         if (i != exclude)
            summa += *vect[i];
     return summa;
  }

  // Приведение типа
  operator T () {
     return sum();
  }

  // Основной оператор присваивания
  T operator = (T value) {
     int index = rand() % size;
     *vect[index] = value - sum(index);
     return value;
  }

  T operator + (T value) { return operator = (sum() + value); }
  T operator - (T value) { return operator = (sum() - value); }
  T operator * (T value) { return operator = (sum() * value); }
  T operator / (T value) { return operator = (sum() / value); }
 
  T operator += (T value) { return operator = (sum() + value); }
  T operator -= (T value) { return operator = (sum() - value); }
  T operator *= (T value) { return operator = (sum() * value); }
  T operator /= (T value) { return operator = (sum() / value); }

  T operator ++ () { return operator = (sum()+1); }
  T operator -- () { return operator = (sum()-1); }
  T operator ++ (int unused) { return operator = (sum()+1); }
  T operator -- (int unused) { return operator = (sum()-1); }

  void print()
  {
     for (int i=0; i<size; i++)
         cout << *vect[i] << " ";
     cout << endl;
  }
  void print_where()
  {
     for (int i=0; i<size; i++)
         cout << vect[i] << endl;
  }
};


* This source code was highlighted with Source Code Highlighter.



Пользуемся нашим шаблоном вот так:
int_x<int> a = 0, b = 7;
// Далее a и b используются как
// обычные переменные типа int

int_x<int> x(0,10,8192);
// Переменная x имеет значение 0,
// хранится в 10 различных переменных,
// между созданием каждого из элементов вектора
// в памяти выделялось от 0 до 8192 байт.
// Далее переменной x пользуемся как int-ом


* This source code was highlighted with Source Code Highlighter.



5. Наблюдаем за работой схемы


Выполним следующий код:
int_x<unsigned short int>
  ab(0,5,4096), a = 3, b(5,3);
ab = 1;

cout << "Address of a : " << endl; a.print_where();
cout << "[ a == " << a << " ]: "; a.print(); cout << endl;
cout << "Address of b : " << endl; b.print_where();
cout << "[ b == " << b << " ]: "; b.print(); cout << endl;
cout << "Address of a^b : " << endl; ab.print_where();
cout << "[ a^b == " << ab << " ]: "; ab.print(); cout << endl;

for (int i=0; i<b; i++)
{
  ab *= a;
  cout << "[ a^b == " << ab << " ]: "; ab.print();
}
cout << ab << endl;


* This source code was highlighted with Source Code Highlighter.



В результате выполнения видим:
Address of a :
0x3e4810
0x3e4820
[ a == 3 ]: 65147 392

Address of b :
0x3e5098
0x3e50a8
0x3e4138
[ b == 5 ]: 64693 400 448

Address of a^b :
0x3e4760
0x3e50c0
0x3e5280
0x3e4798
0x3e40d0
[ a^b == 1 ]: 20672 21120 1 392 23352

[ a^b == 3 ]: 20672 21120 1 392 23354
[ a^b == 9 ]: 20678 21120 1 392 23354
[ a^b == 27 ]: 20696 21120 1 392 23354
[ a^b == 81 ]: 20696 21174 1 392 23354
[ a^b == 243 ]: 20696 21174 163 392 23354
243


P.S.
Вместо операции сложения можно использовать операцию XOR.
Будет чуть быстрее работать и немного запутанней.
Я пожалуй остановлюсь на сложении))

Ну вот и всё. Ничего страшного.
Есть замечания, дополнения, идеи, комментарии?

Читать дальше

пятница, 10 апреля 2009 г.

Виста и Хакинтош на одном диске.

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

1) В первую очередь создаем праймари раздел для хакинтоша и форматируем его как FAT32. Устанавливаем на него хакинтош с переформатированием файловой системы в журналируемую HFS. Помечаем этот раздел как активный.

2) Теперь при включении наблюдаем ошибку "HFS+ Error". Загружаемся с установочного диска хакинтоша. Запускаем утилиту командной строки "Terminal". Набираем команду fdisk -e /dev/rdisk0 (в последней цифре указан номер физического диска, у меня он один и есть - нулевой). Набираем команду p, чтобы увидеть таблицу разделов диска. Далее помечаем раздел с хакинтошем как активный: f 2 (у меня хакинтош на разделе 2). Набираем write и exit.

3) Теперь имеем загружающийся хакинтош. При загрузке нас просят выбрать раздел, с которого следует произвести загрузку. Хакинтош то работает, а виста откинулась.

4) Загружаемся с любого рекавери диска в Partition Magic. С его помощью делаем активным раздел с вистой. С остальных разделов флаг активности необходимо снять.

5) Берём любой установочный диск висты. Абсолютно любой, какая бы виста у вас ни была: на компе, в буке и т.д. Загружаемся с этого диска находим старую инсталляцию на диске и нажимаем восстановить/восстановить загрузчик.

6) Загружаемся опять в партишн мэджик и ставим активным только раздел с макосью.

Имеем при загрузке выбор раздела с осью. Всё как и хотели. А теперь прикинем, почему нам пришлось так извращаться. Кто виноват? Началось всё с того что раздел с хакинтошем должен быть помечен как активный не поросто так, а по "волшебному" через фдиск, при этом он портит MBR, где прописывается виста. Затем "тупить" начинает виста, когда загрузочный диск не может найти предыдущую инсталляцию винды на неактивном разделе. Для этого мы и игрались с партишн мэджиком. В активном разделе уже виста найдёт установку и сможет починить загрузчик. Как вывод: установка раздела активным в fdisk и в Partition Magic - абсолютно разные вещи. Партишн мэджик делает это "более поверхностно".

З.Ы.
Если возникли проблемы/вопросы/комментарии, feel free to write comments))

Читать дальше

среда, 8 апреля 2009 г.

Быстрый перебор всех сочетаний(выборок)

Возникла потребность в "быстром" алгоритме перебора всевозможных размещений K единиц в N разрядах. Немного погуглил, но так и не нашел алгоритмов без дважды вложенных циклов. А ведь хочется получить функцию для "выработки" следующей комбинации на основе предыдущей. Да и хранить единицы и нули желательно не в строках(побайтно), а в многоразрядных числах(побитно). В этом случае, конечно, возникает вопрос разрядности чисел, как ограничение на параметр N ... тогда используем числа разрядности 64, 128, 256 бит и т.д. Например, можно воспользоваться классом big_int в составе библиотеки Boost. Прикинем на глаз всевозможные варианты размещения 3-ёх единиц в 5-ти разрядах и порядок перебора этих вариантов:
1 1 1 0 0
1 1 0 1 0
1 1 0 0 1
1 0 1 1 0
1 0 1 0 1
1 0 0 1 1
0 1 1 1 0
0 1 1 0 1
0 1 0 1 1
0 0 1 1 1
Итого 10 вариантов (число сочетаний из пяти по три). Визуально алгоритм выглядит как пробегающая слева направо единица. Опишем его формально с использованием рекурсии (в данном алгоритме использование рекурсии не желательно, но с ней "красивше"):
1) Если самый правый символ "0",
то находим среди всех единиц самую правую и сдвигаем её на 1 позицию вправо.
2) Если самый правый символ "1",
то отрубаем самый правый символ и отправляем полученную комбинацию (длины N-1 с K-1 единицами) на п.1 алгоритма. В полученном значении находим самую правую единицу и вписываем вырезанную ранее единицу сразу после неё.

При хранении комбинации в многоразрядных переменных нам понадобятся следующие операции:
а) Операция определения значения младшего разряда
(a & 1)
б) Операция сдвига вправо самой младшей единицы, с неприкосновенностью более старших разрядов.
int shiftLast1(int a) {
    return ((a-1) ^ ((a^(a-1)) >> 2));
}
в) Операция дописывания единицы справа от самой младшей единицы.
int add1AfterLast1(int a) {
    return ( a | ( ((a^(a-1)) + 1) >> 2 ) );
}

Теперь метод генерации первой комбинации. K единиц сдвигаются вправо на (N-K) позиций.
int firstSoch(int n, int k) {
    return ( ((1 << k) - 1) << (n - k) );
}

Главный метод для вычисления комбинации реализует описаный нами алгоритм:
int nextSoch(int a)
{
    // в случае последней комбинации вернём нуль
    if ((a & (a+1)) == 0)
    return 0;

    if (a & 1)
        return add1AfterLast1( nextSoch(a >> 1) << 1 );
    else
        return shiftLast1(a);
}

З.Ы.
1) Вместо функций (б) и (в) можно использовать макросы. Думаю функции с одним лишь ретурном компилятор включает "инлайн", тогда разницы с "дефайном" в принципе и нет. (Аккуратнее с вложенным вызовом макросов! - напоролся однако)
2) Аккуратнее с типами констант:
(1 << 48) не равно (0x01000000000000)
(__int64(1) << 48) равно (0x01000000000000)

З.З.Ы.
Если алгоритм вам пригодился или вы имеете интересные замечания/комментарии, как говорится, feel free to comment . . .

Читать дальше