СТАРОЛЕТОВ С.М., к.ф.-м.н., доцент кафедры прикладной математики АлтГТУ имени И.И. Ползунова, serg_soft@mail.ru

Исследование наиболее часто встречающихся ошибок в ядре Linux
путем анализа коммитов в Git-репозитории

Статья посвящена методике анализа наиболее частых ошибок в ядре Linux путем проверки сообщений коммитов разработчиков ядра с использованием библиотеки для работы с Git-репозиторием на программном уровне. Наиболее частые сообщения о коммитах по исправлению ошибок вычисляются с использованием расстояний Левенштейна между текстами сообщений. Показаны способы анализа наиболее релевантных сообщений об ошибках, определения файлов программного кода с наибольшим количеством ошибок и вывод наиболее ошибочных строк кода в этих файлах. Приведены результаты экспериментов на реальных репозиториях, включая главный репозиторий Linux Kernel, подсистему памяти, сетевую подсистему, проект Bluez

Введение

Ядро Linux [1] – очень хороший пример того, как совместная работа людей может решать сложнейшие проблемы. Ядро было изначально написано Линусом Торвальдсом, и к настоящему моменту в нем оставили свой след более 16 000 участников (мы можем получить это значение, посчитав коммиттеров основного репозитория Linux).

Ядро – это набор функций и структур данных в операционной системе, которые выполняют низкоуровневые системные операции, например управление памятью, планирование процессов, поддержка устройств, код сетевой подсистемы и т.д.

Ядро Linux написано на C и использует свою собственную C-библиотеку в качестве программного API.

Одним из преимуществ выпуска программного обеспечения с открытым исходным кодом являются бесплатные отзывы и отчеты об ошибках.

Многие пользователи тестируют новое, только что собранное ядро и сообщают разработчикам об ошибках. На программное обеспечение нет никаких гарантий; люди используют его на свой страх и риск и предоставляют обратную связь.

Инженеры в сообществе могут собирать отчеты, находить проблемы и исправлять такое программное обеспечение; позже это ПО, или его часть, может быть выпущено как стабильная версия (ведь оно уже было протестировано тысячами и миллионами пользователей) и даже может быть использовано в коммерческих системах.

Открытость программного обеспечения в данном случае приводит к его бесплатному тестированию большим числом пользователей, следовательно, вероятность выпуска более или менее стабильного кода повышается.

В настоящее время группы разработчиков программного обеспечения используют системы контроля версий (version control systems, VCS); для разработки ядра Linux используется инструмент Git [2], который является вторым после ядра наиболее известным проектом Линуса Торвальдса. Поскольку VCS могут легко отслеживать любое изменение состояния проекта, включая добавление новой функции, улучшения и исправления ошибки, можно отслеживать исправления, строить статистику для анализа, и данная статья посвящена этому.

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

Часть данной работы была представлена в виде постера на конференции SYRCoSE в Иннополисе [3].

Git и JGit

Для контроля над процессом разработки ядра Линусу понадобилась как распределенная VCS, так и одновременно локальная VCS, которую можно было бы использовать в автономном режиме для отслеживания изменений, создания патчей, просмотра diff (различий между коммитами), merge (слияния) заданных запросов от других разработчиков в то время, например, когда он летит из Европы в Америку на самолете или использует место без доступа к сети. Но в 2005 году такой системы не было (большинство использовало SVN, который требовал подключения к сети для действий с репозиторием), и он решил ее сделать [4].

Сейчас Git де-факто используется в большинстве компаний по разработке программного обеспечения, в которых разработчики, менеджеры и другие члены команды совместно пишут свой код, отслеживают изменения и контролируют процесс разработки.

Коммит (commit) – это действие, когда разработчик программного обеспечения фиксирует в VCS сделанные им изменения. Разработчик берет код из общего репозитория, работает над ним и, когда он думает, что сделал достаточный прогресс, сохраняет изменения в репозитории, выполняя коммит. Каждый коммит приходит с сообщением на естественном языке о сделанных изменениях, которые описывает сам разработчик.

JGit [5] – это библиотека с открытым исходным кодом, написанная на Java для работы с репозиториями Git и обхода внутренних деревьев коммитов.

Она была выбрана в данной работе из-за надлежащей документации и большого количества фрагментов кода в интернете. JGit программно предлагает доступ к коммитам репозитория, к изменениям (diff) в каждом коммите, и мы можем написать код на Java для проведения собственного анализа, который срабатывает в процессе перебора нужных узлов в Git-репозитории.

В нашей работе [6] данная библиотека использовалась для реализации программного обеспечения для контроля деятельности разработчиков по их коммитам. В настоящей работе на базе нее было написано средство для анализа ошибок по текстам исправляющих коммитов.

Постановка задачи

Предположим, что у нас есть локальный Git-репозиторий ядра Linux или связанных с ним источников (технология также может быть применена к любому Git-репозиторию).

Наши цели:

• Найти наиболее частые ошибки. Ее можно переформулировать следующим образом: найти наиболее распространенные сообщения в коммитах с исправлениями, а затем переформулировать так: найти наиболее релевантные сообщения об исправлениях, не обязательно такие же, но похожие.
• Найти исходники с наиболее частыми ошибками. Это можно переформулировать так: найти файлы, которые упоминались в коммитах с сообщением «исправить» чаще всего.

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

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

Нахождение похожих сообщений

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

Здесь строки являются сообщениями исправляющих коммитов, которые содержат слова «Fix» или «Fixed:», от таких начальных символов до конца строки или до конца сообщения. Начала строк вида «Fix» или «Fixed:» были выбраны из-за их нахождения при предварительном просмотре существующих сообщений с коммитами в главном репозитории ядра Linux.

В этой работе используется метрика расстояния Левенштейна [7] (используемая в реализации алгоритма diff) и его реализация [8].

Расстояние Левенштейна вычисляет значение метрики различия между двумя строками в виде целого числа (чем оно меньше, тем строки более похожи). Чтобы найти ближайшую строку к списку заданных строк, мы должны вычислить расстояние Левенштейна между данной строкой и каждой строкой в списке строк и вернуть строку с минимальным расстоянием.

Данное решение выбрано из-за соображений простоты и скорости, также тут можно было бы использовать и меру Жаккара по словам или расстояние Дамерау – Левенштейна. Большое количество сообщений об ошибках и их похожая структура описания позволяют считать незначительными погрешности, связанные с нахождением похожих строк при первоначальной малой базе сообщений.

Алгоритм нахождения наиболее часто встречающихся ошибок в репозитории

В данном разделе представлен алгоритм поиска в виде, близком к нотации Кормена.

algorithm FindMostFrequentErrors (repository, count)

for branch ∈ Branches(repository)

     for commit ∈ Commits (repository, branch, path)
        commitMessage ← Message (commit)

        if commitMessage ∈ ("Fix*", "Fixed:*")

             for otherMessage ∈ messages
                minDst ← min (minDst,
                LevenshteinDistance (
                        commitMessage, otherMessage))
             endfor

 	  closestMessage ← (message ∈ messages |
                LevenshteinDistance (commitMessage, 
                message) == min)
             messages[] ← commitMessage
             mapMsgRelevance [closestMessage] ++
             mapMsgRelevance [commitMessage] ++
             FindMostBuggySources (commit)

        endif

     endfor

endfor

return GetFirst (count, SortMap (mapMsgRelevance))

Здесь:

• repository – это объект JGit, который представляет локальный клонированный Git репозиторий;
• count – максимальное количество ошибок, которые нужно найти;
• Branches представляет все ветви из данного Git-репозитория;
• Commits содержит все коммиты из данного репозитория, данной ветви репозитория и заданного начального пути (мы можем начать поиск не с корня репозитория, а из некоторого каталога внутри него);
• Message возвращает сообщение о коммите из заданного объекта, описывающего коммит;
• LevenshteinDistance вычисляет значение расстояния Левенштейна для двух заданных строк;
• messages – это составленный список уже известных сообщений коммита;
• mapMsgRelevance – внутренний ассоциативный массив, отображение сообщения в его значение релевантности;
• MostBuggySources – алгоритм для решения проблемы поиска исходников с наиболее частыми ошибками;
• GetFirst – ограниченный итерационный алгоритм, который возвращает значения заданного количества первых элементов заданной коллекции;
• SortMap – алгоритм сортировки ассоциативного массива по значению в порядке убывания.

Для поиска исходников с наиболее частыми ошибками (MostBuggySources в псевдокоде) достаточно посчитать в ассоциативном массиве изменения для затронутых в коммитах с исправляющими сообщениями файлов и вывести наиболее встречающиеся. Реализация данных алгоритмов размещена в [9].

Для анализа природы ошибок в исходном кода с наиболее часто встречающимися изменениями или поиска авторов коммитов с ошибками и авторов исправлений можно пользоваться набором команд git log, git blame и git show, это отдельная скрупулезная работа.

Результаты анализа. Общий комментарий

Текущая реализация алгоритмов не является оптимизированной, не распараллелена и не распределена (это, возможно, будет являться предметом дальнейшей работы вместе с трекингом конкретных ошибок, распределения по авторам и функциям), поэтому анализ текущего основного репозитория ядра Linux [10] (более 811 000 коммитов) длится около 10 часов на обычном ноутбуке с Intel Core i5.

Этот анализ дает нам общую статистику по всему ядру. Поскольку разработанное программное обеспечение позволяет выбрать репозиторий и начальный путь в репозитории, можно проанализировать различные связанные с ядром репозитории в [11] или части основного репозитория в соответствующих директориях (управление памятью, работа в сети и т.д.).

Время анализа среднего количества коммитов (20 000) в репозитории составляет около 10 минут.

Итак, далее будут представлены некоторые результаты анализа всего репозитория Linux [10], стека протоколов Bluetooth для Linux (Bluez) [12], части управления памятью и сетевой части из основного репозитория.

Результаты были исправлены из-за некоторых дубликатов (множественное число, знаки и т.д.), во всех результатах показаны первые 10-15 уникальных ошибок из вывода, остальные были отсечены.

Результаты анализа. Анализируем основной репозиторий Linux Kernel

Найденные описанным ПО наиболее релевантные сообщения об ошибках (по убыванию подсчитанного показателя) показаны в таблице 1.

Таблица 1. Основные сообщения об исправленных ошибках по всему репозиторию Linux Kernel

Общий анализ дает нам информацию о том, что наиболее актуальными вопросами являются проблемы интеграции модулей, обработки ошибок, некоторые специфические проблемы компонентов, а также проблемы в коде.

Во-первых, мы можем наблюдать неинформативные сообщения об исправлениях (fixed this, that, it). Они портят статистику, и странно, что разработчики пишут данные описания в проекте такого уровня.

Во-вторых, исправления, выявленные при предупреждениях после статической проверки специальными инструментами, являются наиболее частыми.

Checkpatch.pl [13] – это скрипт для проверки кода в соответствии с рекомендациями ядра Linux. Руководство приведено в источнике [14].

Очень странно, что разработчики, которые создают патч для ядра, первоначально игнорируют этот документ. Ядро представляет собой огромное количество исходных кодов (в основном C-файлов), и если бы каждый разработчик из 16 000 использовал собственный стиль кодирования, проект мог бы стать одним большим беспорядком.

Далее, если перемещаться от уровня кода к уровню логики, современный разработчик проверяет код статическим анализатором, который сможет автоматически найти некоторые типичные ошибки в коде; для ядра Linux был разработан такой специальный анализатор – sparse [15].

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

В-третьих, можно наблюдать большое число исправлений, связанных с обработкой ошибок, автозагрузкой и выгрузкой модулей. Их можно отнести к ошибкам интеграции модуля в окружение Linux. Судя по всему, к настоящему моменту не выработано общепринятых автоматизированных средств по интеграции модулей в разные версии ядер, в системы с разной архитектурой, и ошибки в интеграции ищутся путем тестирования.

Следует также отметить то факт, что интеграционные ошибки по количеству сообщений фиксации в общей статистике занимают более высокое место, чем ошибки, связанные с проблемами в коде.

В-четвертых, в общей статистике на сегодняшний момент фигурируют некоторые ошибки из домена конкретных компонентов ядра Linux. В данном случае это ошибки с вычислением периода (относится к таймерам), именем узлов (символьные устройства), удалением головы списка в планировщике. Видимо, данные компоненты меняются слишком часто и важны для проекта.

И, наконец, это ошибки, специфические для кода и конкретно для языка С. Мы видим здесь в первую очередь ошибку «неинициализированные переменные» – это ошибка, приводящая к непредсказуемому поведению и большому количеству уязвимостей. Тем не менее в рамках всего ядра мы видим не так уж и много одинаковых ошибок, относящихся именно к программированию и к языку С.

На рис. 1 приведены наиболее часто изменяемые файлы по всему репозиторию ядра. Как видно, большинство исправлений в ядре – это улучшения драйверов интегрированной графики от Intel. Такое количество исправлений может говорить как о плохом качестве кода в компании, изначальной непродуманности архитектуры, так и, наоборот, о постоянных модернизациях и оптимизациях с целью сделать реально быструю и корректно работающую графику под Linux.

Рисунок 1. Наиболее частые исправления в файлах исходного кода ядра Linux

Также присутствует большое количество исправлений в криптографической хеш-функции Skein, средстве верификации программ обработки пакетов Berkeley Packet Filter [16], а также и GPU драйвера AMD.

Результаты анализа. Анализируем подсистему памяти

В результате анализа репозитория Linux Kernel в части, ответственной за управление памятью, обнаружены сообщения об исправлениях ошибок, относящихся прежде всего к домену работы с памятью (см. рис. 2).

Рисунок 2. Диаграмма основных сообщений об исправлениях в подсистеме памяти

Основные исправления касаются THP (Transparent HugePages, прозрачные страницы памяти огромного размера) [17], то есть технологии маппинга больших областей памяти для высокопроизводительных приложений, аннотаций для секций памяти, миграций страниц и предупреждения средства sparse.

На рис. 3 приведено количество исправлений в файлах исходных кодов подсистемы памяти. Можно сделать вывод, что наибольшее количество исправлений касается аллокатора памяти, реализующего алгоритм SLUB.

Рисунок 3. Количество исправлений в файлах исходников подсистемы памяти

Результаты анализа. Анализируем сетевую подсистему

В результате анализа сетевой подсистемы (см. рис. 4) обнаружено опять же большое количество исправлений в результате работы анализатора sparse, также присутствуют частые исправления проблем race condition («гонка данных») и утечек памяти, большое количество исправлений уязвимостей протокола TLS.

Рисунок 4. Диаграмма основных сообщений об исправлениях в сетевой подсистеме

На рис 5. показаны исправления в исходных файлах, тут следует отметить огромное количество исправлений по различным сетевым протоколам (Wi-Fi, Bluetooth, MAC, IPv6, IPv4), исправления в ядре и в Netfilter. Сетевая часть подвержена частым исправлениям и оптимизациям.

Рисунок 5. Количество исправлений в файлах исходников сетевой подсистемы

Результаты анализа. Анализируем проект Bluez

Проект Bluez [12] – это открытая реализация стека протокола Bluetooth для Linux, взаимодействующая с Bluetooth-подсистемой в ядре, со звуковыми и другими устройствами. В последнее время с появлением большого количества «умных» устройств в сфере IoT-решений, с передачей высококачественного аудио на носимые устройства, данный протокол активно развивается. Результаты основных исправлений ошибок в проекте Bluez представлены на рис. 6.

Рисунок 6. Диаграмма основных сообщений об исправлениях в Bluez

Этот проект прежде всего интересен большим количеством кода на чистом C, и интересно, что наиболее часто встречающаяся ошибка тут – утечка памяти (такие ошибки характерны и для всей сетевой подсистемы – см. ранее).

Также видны исправления ошибочных действий с уже освобожденной памятью, нулевыми указателями и ошибками в ручном управлении памяти.

Специфическими ошибками для Bluetooth-соединений являются падение при дисконнекте и изменение состояния соединения.

Заключение

Данные Git-репозитория ядра Linux – это огромная бесплатная база знаний информации на естественном языке о процессе разработки большого проекта системного программного обеспечения, тесно связанная с кодом. Показанная методика позволяет сравнительно легко находить наиболее частые похожие сообщения об исправлениях ошибок. Если проанализировать текущие результаты по сравнению с прошлым проведенным исследованием [3], можно отметить большое количество исправлений, связанное с внедрением статического анализатора sparse. Периодическое слежение за ошибками позволяет узнать последние актуальные тенденции в разработке, о сложных проблемах и важных частях данной столь стремительно меняющейся операционной системы.

1. The Linux Kernel Archives. URL: https://www.kernel.org/ (дата обращения: 06.02.2019).
2. Chacon S., Straub B. Pro Git. – Apress, 2014. URL: https://git-scm.com/book/ru/v2 (дата обращения: 06.02.2019).
3. S. Staroletov. A survey of most common errors in Linux Kernel (Poster). DOI: 10.13140/RG.2.2.18768.97280.
4. 10 Years of Git: An Interview with Git Creator Linus Torvalds. URL: https://www.linux.com/blog/10-years-git-interview-git-creator-linus-torvalds/ (дата обращения: 06.02.2019).
5. JGit – Eclipse. URL: https://eclipse.org/jgit/ (дата обращения: 06.02.2019).
6. Амосов М.С., Старолетов C.М. Программное обеспечение для статической обработки данных об изменениях файлов проекта в распределенной системе контроля версий Git. XIV Всероссийская научно-техническая конференция студентов, аспирантов и молодых ученых «Наука и молодежь – 2017». Секция «Информационные технологии». Подсекция «Программная инженерия». / Алт. гос. техн. ун-т им. И.И.Ползунова. – Барнаул: изд-во АлтГТУ, 2017. – C. 108-112. URL: http://edu.secna.ru/media/f/pi2017v3.pdf#page=108 (дата обращения: 06.02.2019).
7. Левенштейн В.И. Двоичные коды с исправлением выпадений, вставок и замещений символов // Доклады Академии наук. – Российская академия наук, 1965. – Т. 163. – №. 4. – С. 845-848.
8. Black, Paul E. Levenshtein distance, Dictionary of Algorithms and Data Structures [online], U.S. National Institute of Standards and Technology. URL: https://xlinux.nist.gov/dads/HTML/Levenshtein.html (дата обращения: 06.02.2019).
9. S.Staroletov. Linux Kernel Analysis. URL: https://github.com/SergeyStaroletov/LinuxKernelAnalysis (дата обращения: 06.02.2019).
10. Linux kernel source tree. URL: https://github.com/torvalds/linux (дата обращения: 06.02.2019).
11. Kernel.org git repositories. URL: https://git.kernel.org (дата обращения: 06.02.2019).
12. Bluetooth protocol stack for Linux. URL: https://git.kernel.org/pub/scm/bluetooth/bluez.git/ (дата обращения: 06.02.2019).
13. Berger R. Howto make a GNU/Linux Kernel Patch. – 2010. URL: https://www.reliableembeddedsystems.com/2010_10_20/WE-2.1_Berger-paper.pdf (дата обращения: 06.02.2019).
14. Linux kernel coding style. URL: https://www.kernel.org/doc/Documentation/process/coding-style.rst.
15. Sparse – a Semantic Parser for C. URL: https://sparse.wiki.kernel.org (дата обращения: 06.02.2019).
16. Reshetova E., Bonazzi F., Asokan N. Randomization can’t stop BPF JIT spray //International Conference on Network and System Security. – Springer, Cham, 2017. – С. 233-247.
17. Transparent Hugepage Support. URL: https://www.kernel.org/doc/Documentation/vm/transhuge.txt (дата обращения: 06.02.2019).

Ключевые слова: ошибки, Linux Kernel, ОС, расстояние Левенштейна, Git.

Researching the most common bugs in the Linux kernel by analysing commits in the Git repository

Staroletov S.M., Ph.D., associate professor at the department of Applied mathematics, Polzunov Altai State Technical University, serg_soft@mail.ru

Abstract: The article is devoted to a method of analysing the most frequent errors in the Linux kernel by checking the messages of Kernel developers’ commits using a library for working with Git repositories at the program level. The most frequent commit messages about error fixes are calculated using the Levenshtein distances between message texts. The article shows ways to analyse the most relevant error messages, identify the program code files with the most errors count, and display the most erroneous lines of code in these files. Presented some results of experiments on real repositories, including the main Linux Kernel repository, the memory subsystem, the network subsystem, the Bluez project.

Keywords: Bugs, Linux Kernel, OS, Levenshtein distance, Git.

Комментарии могут оставлять только зарегистрированные пользователи