Прогнило что-то в датском королевстве
В новой версии (2.3.0-preview1) руби что-то пошло не так. Разработчики MRI поддержали фичу сравнения хэшей по отношению включения при помощи операторов сравнения. Никого не смутило, что это частично упорядоченное множество. Ок, сравнения классов в языке уже живут очень давно. Но для них хотя бы есть специальный результат сравнения несравнимых объектов - nil. Тоже чудовищно плохо, но нынешнее предложение даже еще хуже. Оно с чистым сердцем говорит {a: 1} <= {b: 2} -- false и {b: 2} <= {a: 1} -- тоже false. Программистская и общечеловеческая интуиция говорит, что a=b. А вот теперь фиг!
Вообще отсутствие исключений при сравнении несравнимых объектов дает потрясающие эффекты. Без этого предположения вот такой, кажется, очевидный код:
def qsort(arr)
return arr if arr.size <= 1
pivot = arr[arr.length / 2]
left = arr.reject{|el| el >= pivot }
right = arr.reject{|el| el <= pivot }
central = arr.select{|el| el == pivot }
qsort(left) + central + qsort(right)
end
который нормально сортирует числа, строки, всё что угодно. А вот с массивом классов или хэшей он делает замечательную штуку: он их раскукоживает. Пример:
qsort([String, Fixnum, Hash])
# => [String, Hash, String, Fixnum, String, Hash, String]
qsort( [{}, {a:1,b:2}, {c:3}, {a:1}, {b:2}] )
# => [{}, {:b=>2}, {:a=>1}, {:b=>2}, {:a=>1, :b=>2}, {:c=>3}, {:b=>2}, {:a=>1}, {:b=>2}, {:a=>1, :b=>2}]
А теперь сделаем чуть больше хэшей в массиве. Десять - двадцать пять одноэлементных хэшей. Не бог весть какой объяем данных для сортировки.
Ну ок, быстрая сортировка 25-элементный массив "отсортировала" за минуту, получив 33.5 миллиона элементов. Если получить доступ к похожему рекурсивному методу, DoS обеспечен.
qsort( 10.times.map{|i| {i => i} } ).size # => 1023
qsort( 20.times.map{|i| {i => i} } ).size # => 1048575
qsort( 25.times.map{|i| {i => i} } ).size # => 33554431
Теперь думаю, как бы найти в кодовой базе популярных проектов вектор для подобной атаки. Раньше авторы спокойно могли полагаться на эксепшн "несравнимые объекты", а теперь такие места сурово уязвимы. По сути мне нужно искать либо рекурсивные вызовы (в сериализация где-нибудь может найтись), где за счет неудачных выборок размер частей больше размера целого.
Либо же мне нужно сравнение произвольных пользовательских данных, чтобы пройти в те ветки кода, которые считаются недоступными. Была еще надежда на то, что версии библиотек можно подделывать хэшами. Но если это так, то у Хьюстона гораздо более серьезные проблемы.
Вообще отсутствие исключений при сравнении несравнимых объектов дает потрясающие эффекты. Без этого предположения вот такой, кажется, очевидный код:
def qsort(arr)
return arr if arr.size <= 1
pivot = arr[arr.length / 2]
left = arr.reject{|el| el >= pivot }
right = arr.reject{|el| el <= pivot }
central = arr.select{|el| el == pivot }
qsort(left) + central + qsort(right)
end
который нормально сортирует числа, строки, всё что угодно. А вот с массивом классов или хэшей он делает замечательную штуку: он их раскукоживает. Пример:
qsort([String, Fixnum, Hash])
# => [String, Hash, String, Fixnum, String, Hash, String]
qsort( [{}, {a:1,b:2}, {c:3}, {a:1}, {b:2}] )
# => [{}, {:b=>2}, {:a=>1}, {:b=>2}, {:a=>1, :b=>2}, {:c=>3}, {:b=>2}, {:a=>1}, {:b=>2}, {:a=>1, :b=>2}]
А теперь сделаем чуть больше хэшей в массиве. Десять - двадцать пять одноэлементных хэшей. Не бог весть какой объяем данных для сортировки.
Ну ок, быстрая сортировка 25-элементный массив "отсортировала" за минуту, получив 33.5 миллиона элементов. Если получить доступ к похожему рекурсивному методу, DoS обеспечен.
qsort( 10.times.map{|i| {i => i} } ).size # => 1023
qsort( 20.times.map{|i| {i => i} } ).size # => 1048575
qsort( 25.times.map{|i| {i => i} } ).size # => 33554431
Теперь думаю, как бы найти в кодовой базе популярных проектов вектор для подобной атаки. Раньше авторы спокойно могли полагаться на эксепшн "несравнимые объекты", а теперь такие места сурово уязвимы. По сути мне нужно искать либо рекурсивные вызовы (в сериализация где-нибудь может найтись), где за счет неудачных выборок размер частей больше размера целого.
Либо же мне нужно сравнение произвольных пользовательских данных, чтобы пройти в те ветки кода, которые считаются недоступными. Была еще надежда на то, что версии библиотек можно подделывать хэшами. Но если это так, то у Хьюстона гораздо более серьезные проблемы.