По вашему запросу ничего не найдено :(
Убедитесь, что запрос написан правильно, или посмотрите другие
наши статьи:
Недавно я просматривал некоторые общедоступные репозитории Google на их GitHub. И я заметил, что у них есть репозиторий для непрерывного фаззинга. Я понятия не имел, что такое фаззинг, не говоря уже о непрерывном.
Что же такое фаззинг?
Фаззинг (иногда его называют нечетким тестированием) – это способ автоматического тестирования программного обеспечения. Обычно фаззер вводит в программу большое количество неправильных или случайных входных данных. Таким образом пытаются вызвать сбои, ошибки, утечки памяти и т.д.
Обычно фаззинг лучше всего работает с программами, которые принимают входные данные, такие как веб-сайты, которые могут запрашивать ваше имя или возраст.
Можно попробовать вводить самые различные строки, чтобы попытаться вызвать какие-то проблемы, например, что-нибудь вроде такого: «Power?????????????????? ? ?h ? ??» (это когда-то вызвало аварийный сбой iOS), «??????h??e???????? ???????N??e??z?????p??????e????r????????d??????i??????a?????n?? ?????h??i??v?????-?????m???i????n???? ????????????f ????????c?????????a?????????s?.?? ?Z????????a?????l?????g????????o??.?», «?» или «undefined».
В целом идея фаззинга заключается в том, чтобы попытаться найти пограничные случаи в кодовой базе. Его используют для того, чтобы убедиться, что синтаксический анализ данных, их прием, сохранение и чтение не вызывают ошибок.
Это довольно полноценный тест, поскольку вы можете протестировать весь процесс хранения, например, пробела нулевой длины (U+200B в Юникоде) на своем сайте, чтобы проверить, возникнут ли какие-то проблемы.
Некоторые пытаются внедрить код в поля ввода (это часть фаззинга, которая называется «внедрение кода»), например, в качестве имени.
Злоумышленники не заинтересованы в том, чтобы вы тестировали нестандартный ввод, так как вы можете обнаружить ошибки, которые нарушают работу приложения, а они могли бы использовать их для кражи данных или повторного сбоя в вашем приложении/сервере.
На GitHub есть список под названием «Big List of Naughty Strings» («Большой список сомнительных строк»). Это список строк, которые с большей долей вероятности вызовут проблемы.
Вы можете взглянуть на некоторые в файлах .json и .txt и почитать некоторые комментарии, чтобы понять, почему именно эти строки вызывают проблемы.
Например, некоторые строки написаны вверх ногами «u?op?p?sd?». Есть строки, которые могут быть помечены как ненормативная лексика или как неприемлемые, но на самом деле они к этому не имеют никакого отношения (это называется проблемой Скантропа). И даже есть такие строки, которые могут раскрыть системные файлы, если они вдруг будут проанализированы плохо настроенным синтаксическим анализатором XML.
Кто использует фаззинг?
Как я уже говорил, фаззинг используется в процессе тестирования программного обеспечения для поиска ошибок в ваших программах. Но он также применяется в кибербезопасности и при взломах.
Что касается применения в кибербезопасности, то здесь хакеры пытаются пересечь границу доверия. Граница доверия – это место в компьютерных системах, где данные из доверенного источника передаются из одной области в другую.
В качестве примера давайте представим, что вы получаете имя пользователя в клиентской части, убеждаетесь, что оно является допустимым, а затем передаете его на серверную часть. Ваша граница доверия – это воображаемая линия, по которой данные передаются от клиента к серверу.
Если ваша серверная часть просто «доверяет» данным и не проверяет их (поскольку клиент уже проверил их!), то это может стать проблемой. В случае, если хакеры смогут пройти проверку клиента, они станут поставщиками доверенных входных данных и смогут попытаться вставить туда вредоносные строки.
Именно в этой ситуации фаззинг может посодействовать выборочной проверке, чтобы убедиться, что вы можете выявлять эти проблемы.
Допустим, кто-то должен был фаззить Google Chrome. Один из способов это сделать – запустить браузер в инструменте отладки для того, чтобы отслеживать команды, которые выполняет Chrome, и профилировать его управление памятью.
Позже хакеры направляют программу Chrome, за которой они наблюдают, на один из своих серверов. Их серверы создают миллионы различных веб-страниц, которые Chrome будет загружать. Все эти веб-страницы немного отличаются с точки зрения JS, CSS и HTML. Это нужно для того, чтобы попытаться сломать Chrome, который профилируют хакеры.
Эти хакеры могут осмысленно запускать эти автоматические тесты в течение нескольких месяцев, собирать огромный список журналов Chrome (сбои, любые переполнения памяти и т.д.) и пытаться выяснить, что вызвало сбой.
Просто заставить Chrome «рухнуть» не является их конечной целью. Как только эти хакеры узнают, какие входные данные вызывают сбои, они также могут выяснить, почему эти данные вызывают сбои, и проанализировать, могут ли они использовать эти эксплойты, чтобы исполнить свой зловещий план, или получить доступ к чему-то, к чему доступа у них не должно быть.
На сегодняшний день Google фаззит свои приложения на 30 000 виртуальных машинах! Таким образом, вы вряд ли добьетесь какого-либо успеха, поскольку они очень сильно постарались.
OSS-Fuzz от Google обнаружил более 25 000 ошибок в коде Google Chrome и примерно 22 000 ошибок в других общедоступных кодовых базах, которые используют OSS-Fuzz.
Итак, вернемся к основному заголовку. Кто использует фаззинг? Держу пари, что почти все компании, которые должны защищать свои цифровые активы или информацию, либо наймут тестировщиков для фаззинга своих продуктов, либо будут делать это самостоятельно.
Заключение
Я надеюсь, что эта статья помогла вам понять, что такое фаззинг и для чего он применяется.
Любая программа – это набор инструкций, будь то добавление 2 чисел или отправка запроса по сети. Компиляторы и интерпретаторы берут понятный для человека код и переводят его на машинный язык, который может прочесть компьютер.
В компилируемом языке целевая машина переводит программу самостоятельно. В интерпретируемом языке исходный код не переводится самой машиной; его читает и выполняет другая программа (интерпретатор).
Подробное объяснение
Представьте ситуацию: вы решили приготовить хумус. Но имеющийся у вас рецепт написан на древнегреческом. У вас, как человека не знающего этого языка, есть два варианта.
Вариант 1: кто-то уже перевел этот рецепт на ваш язык. Поэтому вы (и любой человек, знающий ваш язык) сможете прочесть рецепт в переводе и приготовить хумус. Переведенный рецепт и будет компилированной версией.
Есть и другой вариант: у вас есть друг, который знает древнегреческий. Поэтому, решив приготовить хумус, вы пригласили этого друга к себе. Друг сидит рядом и переводит рецепт – строчка за строчкой, – а вы занимаетесь готовкой. Ваш друг – это интерпретатор (переводчик) для интерпретируемой версии рецепта.
Компилируемые языки
Компилируемые языки сразу переводятся в машинный код, который может выполнить процессор. В результате они выполняются быстрее и эффективнее, чем интерпретируемые языки. Кроме того, в таких языках разработчик лучше контролирует аппаратные средства (управление памятью, использование ЦП и т.д.).
Компилируемым языкам требуется дополнительный этап «сборки», при котором их сначала компилируют вручную. Каждый раз при внесении изменений вам нужно будет «пересобирать» программу. Вернемся к примеру с хумусом. Перевод рецепта делался до того, как попал к вам в руки. Если автор рецепта захочет изменить тип оливкового масла, то весь рецепт придется переводить заново, а затем повторно отправлять вам.
Примеры истинных компилируемых языков: C, C++, Erlang, Haskell, Rust и Go.
Интерпретируемые языки
Интерпретаторы проходятся по каждой строке программы и выполняют все команды. Если автор из нашего примера захочет заменить оливковое масло, то он просто зачеркнет старую запись и добавит новую. А затем ваш друг-переводчик сразу увидит это изменение и переведет его вам.
Интерпретируемые языки гораздо медленнее компилируемых. Но с появлением JIT-компиляции (динамической компиляции) эта разница начинает сокращаться.
Примеры популярных интерпретируемых языков: PHP, Ruby, Python и JavaScript.
Небольшое пояснение
В большинстве языков программирования есть компилируемые и интерпретируемые реализации, а сам язык необязательно относится только к компилируемым или интерпретируемым. Но для простоты и удобства их принято относить к тому или иному типу.
Например, Python можно выполнять как компилируемую программу или интерпретируемый язык в интерактивном режиме. А большинство инструментов командной строки, интерфейсов командной строки и оболочек чисто теоретически относятся к интерпретируемым языкам.
Плюсы и минусы
Плюсы компилируемых языков
Обычно программы, скомпилированные в машинный код, выполняются быстрее интерпретируемых. Это связано с тем, что при переводе кода в процессе его выполнения увеличивается потребление ресурсов, что, в свою очередь, замедляет программу.
Минусы компилируемых языков
Основные недочеты компилируемых языков:
нужно больше времени для завершения полной компиляции перед тестированием;
сгенерированный двоичный код зависит от платформы.
Плюсы интерпретируемых языков
Интерпретируемые языки более гибкие и чаще предлагают такие возможности, как динамическая типизация и меньший размер программы. Кроме того, исходный код программы выполняют интерпретаторы, поэтому сам код не зависит от платформы.
Минусы интерпретируемых языков
Самый главный недочет этих языков – скорость выполнения. Она обычно ниже, чем в компилируемых языках.
Алгоритм
– это набор четко сформулированных инструкций, который применяется для решения конкретной задачи. Эти задачи вы можете решать любым удобным для вас способом.
Это значит, что ваш метод, который вы используете для решения задачи, может отличаться от моего, но при этом мы оба должны получить один и тот же результат.
Так как способ решения одной и той же задачи может быть не один, то должен существовать и способ оценить эти решения или алгоритмы с точки зрения оптимальности и эффективности (время, которое требуется для запуска/выполнения вашего алгоритма, и общий объем потребляемой памяти).
Этот этап довольно важный для программистов. Его цель - помочь убедиться, что их приложения работают должным образом, и помочь написать чистый программный код.
И вот здесь на первый план выходит обозначение «О большое». «О большое» - это метрика, которая определяет эффективность алгоритма. Она позволяет оценить, сколько времени занимает выполнение программного кода с различными входными данными, и измерить, насколько эффективно этот программный код масштабируется по мере увеличения размера входных данных.
Что такое «О большое»?
«О большое» показывает сложность алгоритма для наихудшего случая. Для описания сложности алгоритма здесь используются алгебраические выражения.
«О большое» определяет время выполнения алгоритма, показывая, как будет меняться оптимальность алгоритма по мере увеличения размера входных данных. Однако этот показатель не расскажет вам о том, насколько быстро работает ваш алгоритм.
«О большое» измеряет эффективность и оптимальность алгоритма, основываясь на временной и пространственной сложности.
Что такое временная и пространственная сложность?
Один из самых основных факторов, который влияет на оптимальность и эффективность вашей программы – это оборудование, ОС и ЦП, которые вы используете.
Однако при анализе оптимальности алгоритма это не учитывается. Куда важнее учесть временную и пространственную сложность как функцию, которая зависит от размера входных данных.
Временная сложность алгоритма – это то, сколько времени потребуется для выполнения алгоритма в зависимости от размера входных данных. Аналогично пространственная сложность – это то, сколько пространства или памяти потребуется для выполнения алгоритма в зависимости от размера входных данных.
В данной статье мы рассмотрим временную сложность. Эта статья станет для вас своего рода шпаргалкой, которая поможет вам понять, как можно рассчитать временную сложность для любого алгоритма.
Почему временная сложность зависит от размера входных данных?
Для того, чтобы полностью понять, что же такое «зависимость от входных данных», представьте, что у вас есть некий алгоритм, который вычисляет сумму чисел, основываясь на ваших входных данных. Если вы ввели 4, то он сложит 1+2+3+4, и на выходе получится 10; если вы ввели 5, то на выходе будет 15 (то есть алгоритм сложил 1+2+3+4+5).
const calculateSum = (input) => {
let sum = 0;
for (let i = 0; i <= input; i++) {
sum += i;
}
return sum;
};
В приведенном выше фрагменте программного кода есть три оператора:
Давайте посмотрим на картинку выше. У нас есть три оператора. При этом, так как у нас есть цикл, то второй оператор будет выполняться, основываясь на размере входных данных, поэтому, если на входе алгоритм получает 4, то второй оператор будет выполняться четыре раза. А значит, в целом алгоритм выполнится шесть (4+2) раз.
Проще говоря, алгоритм будет выполняться input+2 раза; input может быть любым числом. Это говорит о том, что алгоритм выражается в терминах входных данных. Иными словами, это функция, которая зависит от размера входных данных.
Для понятия «О большое» есть шесть основных типов сложностей (временных и пространственных):
Постоянное время: O1
Линейное время: On
Логарифмическое время: On log n
Квадратичное время: On2
Экспоненциальное время: O2n
Факториальное время: On!
Прежде чем мы перейдем к рассмотрению всех этих временных сложностей, давайте посмотрим на диаграмму временной сложности «О большого».
Диаграмма временной сложности «О большого»
Диаграмма «О большого» - это асимптотические обозначение, которое используется для выражения сложности алгоритма или его оптимальности в зависимости от размера входных данных.
Данная диаграмма помогает программистам определить сценарий наихудшего случая, а также оценить время выполнения и объем требуемой памяти.
Следующий график иллюстрирует сложность «О большого»:
Глядя на приведенную выше диаграмму, можно определить, что O1 – постоянное время выполнения алгоритма, является наилучшим вариантом. Это означает, что ваш алгоритм обрабатывает только один оператор без какой-либо итерации. Дальше идет Olog n , что тоже является неплохим вариантом, и другие:
O1 – отлично/наилучший случай
Olog n – хорошо
On – удовлетворительно
On log n – плохо
On2, O2n, On! – ужасно/наихудший случай
Теперь вы имеете представление о различных временных сложностях, а также можете понять, какие из них наилучшие, хорошие или удовлетворительные, а какие плохие и наихудшие (плохих и наихудших временных сложностей следует избегать).
Следующий вопрос, который может прийти на ум: «какой алгоритм какую сложность имеет?» И это вполне логичный вопрос, ведь эта статья задумывалась как шпаргалка. ?
Когда ваши расчеты не зависят от размера входных данных, то это постоянная временная сложность - O1.
Когда размер входных данных уменьшается в два раза, например, при итерации, обработке рекурсии и т.д., то это логарифмическая временная сложность - Olog n .
Когда у вас один цикл в алгоритме, то это линейная временная сложность - On.
Когда у вас есть вложенные циклы, то есть цикл в цикле, то это квадратичная временная сложность - On2.
Когда скорость роста удваивается при каждом добавлении входных данных, то это экспоненциальная временная сложность - O2n.
Давайте перейдем к описанию временных сложностей. Для каждой будут приведены примеры. Отмечу, что в примерах я использовал JavaScript, но если вы понимаете принцип и что из себя представляет каждая временная сложность, то не имеет значения, какой язык программирования вы выберите.
Примеры временных сложностей «О большого»
Постоянное время: O1
Когда алгоритм не зависит от размера входных данных n, то говорят, что он имеет постоянную временную сложность порядка O1. Это значит, что время выполнения алгоритма всегда будет одним и тем же, независимо от размера входных данных.
Допустим, что задача алгоритма – вернуть первый элемент массива. Даже если массив состоит из миллиона элементов, временная сложность будет постоянной, если использовать следующий подход для решения задачи:
const firstElement = (array) => {
return array[0];
};
let score = [12, 55, 67, 94, 22];
console.log(firstElement(score)); // 12
Приведенная выше функция выполняет лишь один шаг, а это значит, что функция работает за постоянное время, и ее временная сложность O1.
Однако, как уже было сказано, разные программисты могут найти разные способы решения задачи. Например, другой программист может решить, что сначала надо пройти по массиву, а затем уже вернуть первый элемент:
const firstElement = (array) => {
for (let i = 0; i < array.length; i++) {
return array[0];
}
};
let score = [12, 55, 67, 94, 22];
console.log(firstElement(score)); // 12
Это просто пример – вряд ли кто-то будет решать эту задачу таким способом. Но здесь уже есть цикл, а значит алгоритм не будет выполняться за постоянное время, здесь в игру вступает линейное время с временной сложностью On.
Линейное время: On
Линейная временная сложность возникает, когда время работы алгоритма увеличивается линейно с размером входных данных. Когда функция имеет итерацию по входному значению n, то говорят, что она имеет временную сложность порядка On.
Допустим, алгоритм должен вычислить и вернуть факториал любого числа, которое вы введете. Это значит, что если вы введете число 5, то алгоритм должен выполнить цикл и умножить 1·2·3·4·5, а затем вывести результат – 120:
const calcFactorial = (n) => {
let factorial = 1;
for (let i = 2; i <= n; i++) {
factorial = factorial * i;
}
return factorial;
};
console.log(calcFactorial(5)); // 120
Тот факт, что время выполнения алгоритма зависит от размера входных данных, подразумевает наличие линейной временной сложности порядка On.
Логарифмическое время: Olog n
Это чем-то похоже на линейную временную сложность. Однако здесь время выполнения зависит не от размера входных данных, а от их половины. Когда размер входных данных уменьшается на каждой итерации или шаге, то говорят, что алгоритм имеет логарифмическую временную сложность.
Такой вариант считается вторым сверху списка лучших, так как ваша программа работает лишь с половиной входных данных. И при всем при этом, размер входных данных уменьшается с каждой итерацией.
Отличный пример – функция бинарного поиска, которая делит отсортированный массив, основываясь на искомом значения.
Допустим, что нам надо найти индекс определенного элемента в массиве с помощью алгоритма бинарного поиска:
const binarySearch = (array, target) => {
let firstIndex = 0;
let lastIndex = array.length - 1;
while (firstIndex <= lastIndex) {
let middleIndex = Math.floor((firstIndex + lastIndex) / 2);
if (array[middleIndex] === target) {
return middleIndex;
}
if (array[middleIndex] > target) {
lastIndex = middleIndex - 1;
} else {
firstIndex = middleIndex + 1;
}
}
return -1;
};
let score = [12, 22, 45, 67, 96];
console.log(binarySearch(score, 96));
Приведенный выше программный код демонстрирует бинарный поиск. Судя по нему, вы сначала получаете индекс среднего элемента вашего массива, дальше вы сравниваете его с искомым значением и, если они совпадают, то вы возвращаете этот индекс. В противном случае, если они не совпали, вы должны определить, искомое значение больше или меньше среднего, чтобы можно было изменить первый и последний индекс, тем самым уменьшив размер входных данных в два раза.
Так как на каждой такой итерации размер входных данных уменьшается в два раза, то данный алгоритм имеет логарифмическую временную сложность порядка Olog n .
Квадратичное время: On2
Когда в алгоритме присутствуют вложенные циклы, то есть цикл в цикле, то временная сложность уже становится квадратичной, и здесь нет ничего хорошего.
Представьте, что у вас есть массив из n элементов. Внешний цикл будет выполняться n раз, а внутрениий – n раз для каждой итерации внешнего цикла, и, соответственно, общее количество итераций составит n2. Если в массиве было 10 элементов, то количество итераций будет 100 (102).
Ниже приведен пример, где сравниваются элементы для того, чтобы можно было вывести индекс, когда найдутся два одинаковых:
const matchElements = (array) => {
for (let i = 0; i < array.length; i++) {
for (let j = 0; j < array.length; j++) {
if (i !== j && array[i] === array[j]) {
return `Match found at ${i} and ${j}`;
}
}
}
return "No matches found ?";
};
const fruit = ["?", "?", "?", "?", "?", "?", "?", "?", "?", "?"];
console.log(matchElements(fruit)); // "Match found at 2 and 8"
В этом примере есть вложенный цикл, а значит, здесь будет квадратичная временная сложность порядка On2.
Экспоненциальное время: O2n
Экспоненциальная временная сложность появляется, когда скорость роста удваивается с каждым добавлением входных данных n, например, когда вы обходите все подмножества входных элементов. Каждый раз, когда единицу входных данных увеличивают на один, то количество итераций, которые выполняет алгоритм, увеличиваются в два раза.
Хороший пример – рекурсивная последовательность Фибоначчи. Допустим, дано число, и необходимо найти n-ый элемент последовательности Фибоначчи.
Последовательность Фибоначчи – это математическая последовательность, в которой каждое число является суммой двух предыдущих; первые два числа – 0 и 1. Третье число – 1, четвертое – 2, пятое – 3 и т.д. (0, 1, 1, 2, 3, 5, 8, 13, …).
Соответственно, если вы введете число 6, то выведется 6-й элемент в последовательности Фибоначчи – 8:
const recursiveFibonacci = (n) => {
if (n < 2) {
return n;
}
return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2);
};
console.log(recursiveFibonacci(6)); // 8
Приведенный выше алгоритм задает скорость роста, которая удваивается каждый раз, когда добавляются входные данные. А значит, данный алгоритм имеет экспоненциальную временную сложность порядка O2n.
Заключение
Из данной статьи вы узнали, что такое временная сложность, как определить оптимальность алгоритма с помощью «О большого», а также рассмотрели различные временные сложности с примерами.