Java Area конструктор зависает для определенных кривых - PullRequest
Новая
       7

Java Area конструктор зависает для определенных кривых

0 голосов
/ 12 мая 2018

Конструктор Area(Shape) зависает для некоторых странных аргументов Shape, как показано ниже. Каждая закомментированная строка зависает, и не закомментированная строка не висит. Я вижу это поведение с Oracle Java 8 и 10. 

import java.awt.geom.*;

public static void main(String[] args) {
    // new Area(new CubicCurve2D.Double(0, Double.POSITIVE_INFINITY, 0, 0, 0, 0, 1, 0));
    new Area(new CubicCurve2D.Double(0, Double.POSITIVE_INFINITY, 0, 0, 0, 0, 0, 0));
    new Area(new CubicCurve2D.Double(0, Double.NEGATIVE_INFINITY, 0, 0, 0, 0, 1, 0));
    new Area(new CubicCurve2D.Double(0, Double.MAX_VALUE, 0, 0, 0, 0, 1, 0));
    new Area(new CubicCurve2D.Double(0, Double.MIN_VALUE, 0, 0, 0, 0, 1, 0));
    new Area(new CubicCurve2D.Double(0, Double.NaN, 0, 0, 0, 0, 1, 0));

    // new Area(new CubicCurve2D.Double(1, 0, 0, 0, 0, 0, 0, Double.POSITIVE_INFINITY));
    new Area(new CubicCurve2D.Double(0, 0, 0, 0, 0, 0, 0, Double.POSITIVE_INFINITY));

    // new Area(new QuadCurve2D.Double(0, Double.POSITIVE_INFINITY, 0, 0, 1, 0));
    new Area(new QuadCurve2D.Double(0, Double.POSITIVE_INFINITY, 0, 0, 0, 0));
    new Area(new QuadCurve2D.Double(0, Double.NEGATIVE_INFINITY, 0, 0, 1, 0));
    new Area(new QuadCurve2D.Double(Double.POSITIVE_INFINITY, 0, 0, 0, 0, 1));

    // new Area(new QuadCurve2D.Double(1, 2, 3, 4, 5, Double.POSITIVE_INFINITY));
    new Area(new QuadCurve2D.Double(0, 1, 2, 3, 4, Double.POSITIVE_INFINITY));

    // new Area(new QuadCurve2D.Double(1, 0, 0, 0, 0, Double.POSITIVE_INFINITY));
    new Area(new QuadCurve2D.Double(0, 0, 0, 0, 0, Double.POSITIVE_INFINITY));

    // new Area(new QuadCurve2D.Float(1, 0, 0, 0, 0, Float.POSITIVE_INFINITY));
    new Area(new QuadCurve2D.Float(0, 0, 0, 0, 0, Float.POSITIVE_INFINITY));

    Path2D path = new Path2D.Double();
    path.moveTo(1, 0);
    path.quadTo(0, 0, 0, Double.POSITIVE_INFINITY);
    // new Area(path);

    new Area(new Line2D.Double(0, Double.POSITIVE_INFINITY, 0, 0));
    new Area(new Ellipse2D.Double(0, Double.POSITIVE_INFINITY, 0, 0));
}

Что в мире здесь происходит? Существуют ли другие Shape, которые вызывают зависание конструктора Area?

Основной вопрос: игнорирование CubicCurve2D, QuadCurve2D и Path2D объектов с Double.POSITIVE_INFINITY или Float.POSITIVE_INFINITY для любой координаты (я буду иметь дело с такими как случай края), могу ли я безопасно Предположим, что конструктор Area никогда не зависнет?

Обратите внимание, что я не могу применить стандартные методы отладки к этой проблеме, потому что у меня нет доступа к исходному коду Oracle Area, поэтому все, что я могу сделать, это рассматривать его как черный ящик. Мне интересно, есть ли другие известные входные данные, которые вызывают зависание этого черного ящика.

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

1 Ответ

0 голосов
/ 16 мая 2018

Поскольку вы передаете Integer.POSITIVE_INFINITY в качестве аргумента, Java API в итоге генерирует NaN s (не число) в расчете, что приводит к infinite loop

Все вышеперечисленные методы имеют следующую Stacktrace после приостановки потока 

Thread [main] (Suspended)   
    Order1(Curve).compareTo(Curve, double[]) line: 935  
    Order1.compareTo(Curve, double[]) line: 221 
    Edge.compareTo(Edge, double[]) line: 90 
    AreaOp$NZWindOp(AreaOp).pruneEdges(Vector) line: 278    
    AreaOp$NZWindOp(AreaOp).calculate(Vector, Vector) line: 159 
    Area.pathToCurves(PathIterator) line: 195   
    Area.<init>(Shape) line: 126    
    AreaTest.main(String[]) line: 8

По отладчику в Order1(Curve).compareTo(Curve, double[]) line: 935 выполняется бесконечный цикл из строки 935 to line 945, поскольку у нас нет исходного кода, и этот класс не был скомпилирован с отладочной информацией, и мы не можем точно полагаться на номера строк. Однако мы можем посмотреть эти строки в OpenJDK source.

Примечание: Order1(Curve).compareTo метод из суперкласса Order1 Curve

Ниже приведен код, где генерируется NaN 

sun.awt.geom.Curve.compareTo

Oracle JDK decompile code (Enhanced class decompiler)

    //Renamed variables with INFINITY. prefix to signify that their value is INTEGER.POSITIVE_INFINITE
    label101:
    for (arg30 = arg2 + arg24; arg30 <= INFINITY.arg4; arg30 += INFINITY.arg26) {
        if (!this.fairlyClose(this.XforY(arg30), arg0.XforY(arg30))) {
            NaN.arg30 -= INFINITY.arg26;

OpenJDK source code

    while (y <= y1) {
        if (fairlyClose(this.XforY(y), that.XforY(y))) {
            if ((bump *= 2) > maxbump) {
                bump = maxbump;
            }
        } else {
            NaN.y -= INFINITY.bump;

Строка Oracle NaN.arg30 -= INFINITY.arg26; или строка OpenJDK y -= INFINITY.bump; будет генерировать NaN на второй итерации, поскольку INFINITY - INFINITY равно NaN.

Давайте посмотрим на следующее быстро

  1. Любая логическая операция, включающая NaN, всегда приводит к false
  2. Любая арифметическая операция всегда приводит к NaN

Теперь следует бесконечный цикл 

sun.awt.geom.Curve.compareTo

//Renamed variables with INFINITY. and NaN. prefix to signify their value as NaN or INFINITY

Oracle JDK decompile code (Enhanced class decompiler)

    while (true) {
        INFINITY.arg26 /= 2.0D;
        NaN.arg32 = NaN.arg30 + INFINITY.arg26;

        //Loop termination condition is always false, due to NaN in logical operation
        if (NaN.arg32 <= NaN.arg30) {
            break label101;
        }

        if (this.fairlyClose(this.XforY(NaN.arg32), arg0.XforY(NaN.arg32))) {
            NaN.arg30 = NaN.arg32;
        }
    }

OpenJDK source code

    while (true) {
        bump /= 2;
        double NaN.newy = NaN.y + NaN.bump;

        //Loop termination condition is always false, due to NaN in logical operation
        if (NaN.newy <= NaN.y) {
            break;
        }
        if (fairlyClose(this.XforY(newy), that.XforY(newy))) {
            y = newy;
        }
    }

Условие завершения цикла заканчивается введением NaN в условие, которое всегда приводит к ложному результату, потому что этот цикл никогда не прерывается.

Ссылка на код OpenJDK http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b27/sun/awt/geom/Curve.java#936

Примечание: Я тестировал тот же код на openjdk version "1.8.0_151", и он тоже там висит.

Ниже приведены мои предложения по обработке

  1. Тайм-аут - лучшая стратегия. Вы также должны обнаружить использование ресурсов, таких как ОЗУ, диск и использование сети. Если вы запускаете код из непроверенных источников, его обязательно следует запускать в отдельном процессе, а не только в том, что он должен выполняться в отдельной среде, как в контейнере Docker. Измерение времени ожидания / использования ресурсов используется большинством онлайн-соревнований по программированию, таких как CodeChef. Вы можете попробовать запустить бесконечный цикл на https://ideone.com и увидеть, что он заканчивается довольно быстро, скорее всего из-за тайм-аута. Даже контейнер не является надежным, и непроверенный код может использовать уязвимость вашего контейнера и получить доступ к хосту. Оформить заказ этого видео https://youtu.be/rfjmeakbeH8?t=2035, Я отметил текущее время в видео, где показаны стратегии изоляции контейнеров.

  2. Нет другой стратегии :) это проблема остановки из информатики, которая является NP Hard , то есть, вероятно, пока нет решения за полиномиальное время.

...