VPF::Уязвимость класса из примера из книги

MarkHunt

Дата 7.3.2013, 15:33 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 23
Регистрация: 7.3.2013

Репутация: нет
Всего: нет

Здравствуйте!
Есть вот пример, в котором реализуется сортировка чисел типа double. Пример взят из книги Java Programming Language

Код


final class SortMetrics implements Cloneable {

  public long probeCnt, compareCnt, swapCnt;

  public void init() {
    probeCnt = compareCnt = swapCnt = 0;
  }

  public String toString() {
    return probeCnt + " probes " + compareCnt + " compares " + swapCnt + " swaps;";
  }

  public SortMetrics clone() {
    try {
      return (SortMetrics) super.clone();
    } catch (CloneNotSupportedException ex) {
      throw new InternalError(ex.toString());
    }
  }

}

Код


abstract class SortDouble {

  private double[] values;
  private final SortMetrics curMetrics = new SortMetrics();

  /**
   * Invoked to do the full sort
   */
  public final SortMetrics sort(double[] data) {
    values = data;
    curMetrics.init();
    doSort();
    return getMetrics();
  }

  public final SortMetrics getMetrics() {
    return curMetrics.clone();
  }

  /**
   * For extended classes to know the number of elements
   */
  protected final int getDataLength() {
    return values.length;
  }

  /**
   * For extended classes to probe elements
   */
  protected final double probe(int i) {
    curMetrics.probeCnt++;
    return values[i];
  }

  /**
   * For extended classes to compare elements
   */
  protected final int compare(int i, int j) {
    curMetrics.compareCnt++;
    double d1 = values[i];
    double d2 = values[j];
    if (d1 == d2)
      return 0;
    else
      return (d1 < d2 ? -1 : 1);
  }

  /**
   * For extended classes to swap elements
   */
  protected final void swap(int i, int j) {
    curMetrics.swapCnt++;
    double tmp = values[i];
    values[i] = values[j];
    values[j] = tmp;
  }

  /**
   * Extended classes implement this -- used by sort
   */
  protected abstract void doSort();


}

Код


class SimpleSortDouble extends SortDouble {
  protected void doSort() {
    for (int i = 0; i < getDataLength(); i++) {
      for (int j = i + 1; j < getDataLength(); j++) {
        if (compare(i, j) > 0) {
          swap(i, j);
        }
      }
    }
  }
}

Код


public class TestSort {
  static double[] testData = {0.3, 1.3e-2, 7.9, 3.17};

  public static void main(String[] args) {
    SortDouble bsort = new SimpleSortDouble();
    SortMetrics metrics = bsort.sort(testData);
    System.out.println("Metrics: " + metrics);
    for (int i = 0; i < testData.length; i++)
      System.out.println("\t" + testData[i]);
  }
}

класс SortDouble при выполнении операций probe(), compare() и swap() увеличивает соответчвующие счётчики класса SortMetrics, чтобы производить измерения о кол-ве выполненных операций. Казалось бы эти счётчики полностью защищены от внешних воздействий. Но утверждается, что есть уязвимость в SortDouble с помощью которой можно повлиять на счётчики, с целью получения неверного результата. По условию, "программист-злоумышленник" smile

реализующий сортировку в классе, который наследуется от SortDouble, может повлиять на счётчики.
У меня была мысль - в сортировке вызвать swap() 3 раза вместо одного (при этом счётчик свопа показывает якобы неверные данные после сортировки), но это помоему не то что нужно. В общем нужно найти уязвимость в классе SortDouble и исправить её...
заранее спасибо, всем кто откликнется!

Stolzen

Дата 7.3.2013, 18:08 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1041
Регистрация: 17.10.2005

Репутация: 23
Всего: 48

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

--------------------

datatalks.ru - анализ данных, статистика, машинное обучение

MarkHunt

Дата 7.3.2013, 19:17 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 23
Регистрация: 7.3.2013

Репутация: нет
Всего: нет

в SimpleSortDouble эти открытые поля невозможно достать, т.к. поле curMetrics из SortDouble объявлено как private. Даже если воспользоваться методом getMetrics, то всё равно мы эти поля не достанем, т.к. getMetrics нам вернёт клонированный объект, а не текущий.

MarkHunt

Дата 8.3.2013, 15:53 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 23
Регистрация: 7.3.2013

Репутация: нет
Всего: нет

Нашёл решение этой задачи здесь.

Чтобы показать уязвимость класса, предлагается сделать так

Код


class SimpleSortDouble extends SortDouble {

  private boolean inSortAlready = false;

  protected void doSort() {
    if (inSortAlready)
      return;
    reallySort();
    inSortAlready = true;
    super.sort(new double[0]);
    inSortAlready = false;
  }

  private void reallySort() {
    for (int i = 0; i < getDataLength(); i++) {
      for (int j = i + 1; j < getDataLength(); j++) {
        if (compare(i, j) > 0) {
          swap(i, j);
        }
      }
    }
  }

}

т.е. для "обмана" здесь sort() вызвается рекурсивно из super класса. При этом обнуляются все счётчики, т.к. в sort() вызывается init().
Результат работы оригинальной программы

Код


Metrics: 0 probes 6 compares 2 swaps;
    0.013
    0.3
    3.17
    7.9

и результат работы после "хака"

Код


Metrics: 0 probes 0 compares 0 swaps;
    0.013
    0.3
    3.17
    7.9

На форуме предложили такое решение этой проблемы

Код


public final SortMetrics sort(double[] data) {
    if (!is_sorting) {
      is_sorting = true;
      values = data;
      curMetrics.init();
      doSort();
      is_sorting = false;
    } else {
      throw new IllegalStateException("Not allowed to call sort() recursively.");
      // Not allowed to call sort() recursively.
      // This is to prevent doSort() calling sort()
      // with an empty data[] array which will cause
      // curMetrics to have 0's for metrics.
    }
    return getMetrics();
  }

т.е. запретить вызывать sort() рекурсивно.
Но как по мне, то можно сделать и попроще, просто убрать init() из сорта

Код


public final SortMetrics sort(double[] data) {
    values = data;
//    curMetrics.init();
    doSort();
    return getMetrics();
  }

Чтобы было легче нагуглить это решение, приведу здесь условие задания

Цитата

Find at least one security hole in SortDouble that would let a sorting algorithm cheat on its metrics without getting caught. Fix the security hole. Assume that the sorting algorithm author doesn't get to write main.

Цитата

Найдите в SortDouble по меньшей мере одну лазейку, которая позволяет алгоритму
сортировки незаметно изменять значения измеренных параметров. Закройте ее.
Предполагается, что автор алгоритма сортировки не собирается писать метод main.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Java: Общие вопросы \| Следующая тема »