Здравствуйте!
Есть вот пример, в котором реализуется сортировка чисел типа 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 с помощью которой можно повлиять на счётчики, с целью получения неверного результата. По условию, "программист-злоумышленник"  реализующий сортировку в классе, который наследуется от SortDouble, может повлиять на счётчики.
У меня была мысль - в сортировке вызвать swap() 3 раза вместо одного (при этом счётчик свопа показывает якобы неверные данные после сортировки), но это помоему не то что нужно. В общем нужно найти уязвимость в классе SortDouble и исправить её...
заранее спасибо, всем кто откликнется! |