Основные принципы программирования: стек и куча
Авторизуйтесь
Основные принципы программирования: стек и куча
Мы используем всё более продвинутые языки программирования, которые позволяют нам писать меньше кода и получать отличные результаты. За это приходится платить. Поскольку мы всё реже занимаемся низкоуровневыми вещами, нормальным становится то, что многие из нас не вполне понимают, что такое стек и куча, как на самом деле происходит компиляция, в чём разница между статической и динамической типизацией, и т.д. Я не говорю, что все программисты не знают об этих понятиях — я лишь считаю, что порой стоит возвращаться к таким олдскульным вещам.
Сегодня мы поговорим лишь об одной теме: стек и куча. И стек, и куча относятся к различным местоположениям, где происходит управление памятью, но стратегия этого управления кардинально отличается.
Стек — это область оперативной памяти, которая создаётся для каждого потока. Он работает в порядке LIFO (Last In, First Out), то есть последний добавленный в стек кусок памяти будет первым в очереди на вывод из стека. Каждый раз, когда функция объявляет новую переменную, она добавляется в стек, а когда эта переменная пропадает из области видимости (например, когда функция заканчивается), она автоматически удаляется из стека. Когда стековая переменная освобождается, эта область памяти становится доступной для других стековых переменных.
Из-за такой природы стека управление памятью оказывается весьма логичным и простым для выполнения на ЦП; это приводит к высокой скорости, в особенности потому, что время цикла обновления байта стека очень мало, т.е. этот байт скорее всего привязан к кэшу процессора. Тем не менее, у такой строгой формы управления есть и недостатки. Размер стека — это фиксированная величина, и превышение лимита выделенной на стеке памяти приведёт к переполнению стека. Размер задаётся при создании потока, и у каждой переменной есть максимальный размер, зависящий от типа данных. Это позволяет ограничивать размер некоторых переменных (например, целочисленных), и вынуждает заранее объявлять размер более сложных типов данных (например, массивов), поскольку стек не позволит им изменить его. Кроме того, переменные, расположенные на стеке, всегда являются локальными.
В итоге стек позволяет управлять памятью наиболее эффективным образом — но если вам нужно использовать динамические структуры данных или глобальные переменные, то стоит обратить внимание на кучу.
Куча — это хранилище памяти, также расположенное в ОЗУ, которое допускает динамическое выделение памяти и не работает по принципу стека: это просто склад для ваших переменных. Когда вы выделяете в куче участок памяти для хранения переменной, к ней можно обратиться не только в потоке, но и во всем приложении. Именно так определяются глобальные переменные. По завершении приложения все выделенные участки памяти освобождаются. Размер кучи задаётся при запуске приложения, но, в отличие от стека, он ограничен лишь физически, и это позволяет создавать динамические переменные.
Вы взаимодействуете с кучей посредством ссылок, обычно называемых указателями — это переменные, чьи значения являются адресами других переменных. Создавая указатель, вы указываете на местоположение памяти в куче, что задаёт начальное значение переменной и говорит программе, где получить доступ к этому значению. Из-за динамической природы кучи ЦП не принимает участия в контроле над ней; в языках без сборщика мусора (C, C++) разработчику нужно вручную освобождать участки памяти, которые больше не нужны. Если этого не делать, могут возникнуть утечки и фрагментация памяти, что существенно замедлит работу кучи.
В сравнении со стеком, куча работает медленнее, поскольку переменные разбросаны по памяти, а не сидят на верхушке стека. Некорректное управление памятью в куче приводит к замедлению её работы; тем не менее, это не уменьшает её важности — если вам нужно работать с динамическими или глобальными переменными, пользуйтесь кучей.
Заключение
Вот вы и познакомились с понятиями стека и кучи. Вкратце, стек — это очень быстрое хранилище памяти, работающее по принципу LIFO и управляемое процессором. Но эти преимущества приводят к ограниченному размеру стека и специальному способу получения значений. Для того, чтобы избежать этих ограничений, можно пользоваться кучей — она позволяет создавать динамические и глобальные переменные — но управлять памятью должен либо сборщик мусора, либо сам программист, да и работает куча медленнее.
Стек, очередь и куча
На рисунке вы можете видеть обобщенную модель организации памяти компьютера.
Стек — это область памяти, которую вы, как программист, не контролируете никоим образом. В неё записываются переменные и информация, которые создаются в результате вызова любых функций. Когда функция заканчивает работу, то вся информация о ее вызов и ее переменные удаляются из стека автоматически.
Но важнее даже не это, а то, что стек — это структура данных, которая работает по принципу «последним пришел — первым ушел» (last in first out, LIFO). На лекции Дэвид предложил представление стека, как стопки подносов в столовой. Поднос, который попал в стопку последним, новый клиент столовой возьмет в первую очередь.
Над стеком можно осуществлять две операции: push (занесение данных) и pop (изъятие данных).
Пример реализации стека языке С приведен ниже. В этом примере, стек — это просто массив строк, имеет определенную емкость (CAPACITY), и текущий размер (size):
Для реализации операции pop, необходимо проверить, не пустой стек, уменьшить текущий размер на единицу и вернуть элемент.
Очередь
Очередь (queue) — это структура данных, которая напоминает обычную очередь. То есть, в отличие от стека, она работает по принципу «первым пришел — первым ушел» (first in first out, FIFO).
Для очереди определены две операции: добавление элемента в конец очереди (enqueue) и изъятие элемента с начала очереди (dequeue).
В примере объявлена очередь, которая, по сути, представляет собой массив строк:
Чтобы реализовать операцию enqueue, необходимо убедиться, что очередь, не переполнена, добавить элемент в конец очереди и увеличить текущий размер на единицу.
Чтобы реализовать операцию dequeue, надо убедиться, что очередь не пуста, увеличить head на единицу, уменьшить текущий размер и вернуть первый элемент очереди.
Куча и переполнение буфера
Куча (heap) — область памяти, которую контролируют непосредственно программисты. Над которой вы, как программисты, получаете непосредственный контроль. Память здесь выделяется в результате вызова функции malloc.
Более глубокие знания о стеке и куче вам пока не понадобятся. Вы их получите позже, если захотите изучать программирование и компьютерные науки глубже.
Буфер — это массив определенной длины, расположенный в памяти. Переполнение буфера (buffer overflow) возникает, если мы пытаемся записать в него больше данных, чем предусмотрено размером этого массива. С помощью переполнения буфера злоумышленник может записать опасный код в память компьютера.
Обзор Stack Memory
Стековая память — это раздел памяти, используемый функциями c целью хранения таких данных, как локальные переменные и параметры, которые будут использоваться вредоносным ПО для осуществления своей злонамеренной деятельности на взломанном устройстве.
Эта статья является третьей в серии из четырех частей, посвященных x64dbg:
Часть 3. Обзор Stack Memory (мы здесь)
Часть 4. Анализ вредоносного ПО с помощью x64dbg
Что такое стековая память?
Стековую память часто называют LIFO (last in, first out; «последним пришёл — первым вышел»). Представьте ее как стопку строительных кирпичей, уложенных друг на друга: вы не можете взять кирпич из середины, так как стопка упадет, поэтому сначала нужно брать самый верхний кирпич. Так работает стек.
В предыдущей статье мы объяснили, что такое регистры в x64dbg, а также разобрали некоторые основные ассемблерные инструкции. Эта информация необходима для понимания работы стека. Когда в стек добавляются новые данные, вредоносная программа использует команду PUSH. Чтобы удалить элемент из стека, вирус использует команду POP. Данные также могут быть выведены из стека в регистр.
Регистр «ESP» используется для обозначения следующего элемента в стеке и называется «указателем стека».
EBP (он же «указатель кадра») служит неизменной точкой отсчета для данных в стеке. Этот регистр позволяет программе определить, насколько далеко от этой точки находится элемент стека. Так, если переменная находится на расстоянии двух «строительных блоков», то это [EBP+8], так как каждый «блок» в стеке равен 4 байтам.
Каждая функция в программе будет генерировать собственный стековый кадр для ссылки на свои переменные и параметры с использованием этого метода.
Архитектура стековой памяти
Следующая схема поможет проиллюстрировать, как стек формируется подобно набору строительных блоков:
Низкие адреса памяти расположены вверху, а высокие адреса — внизу.
Каждая функция генеририрует собственный стековый кадр, поэтому стековый кадр в приведенном выше примере может накладываться на другой кадр, который используется для другой функции.
EBP, как упоминалось ранее, хранится в качестве неизменной точки отсчета в стеке — это делается путем перемещения значения ESP (указателя стека) в EBP. Мы делаем это, поскольку ESP будет меняться, так как он всегда указывает на вершину стека. Хранение его в EBP дает нам неизменную точку отсчета в стеке, и теперь функция может ссылаться на свои переменные и параметры в стеке из этого места.
В этом примере переданные в функцию параметры хранятся в [EBP]+8, [EBP]+12 и [EBP]+16. Поэтому, когда мы видим [EBP]+8, это расстояние в стеке от EBP.
Переменные будут сохраняться после начала выполнения функции, поэтому они будут располагаться выше по стеку, но в более низком адресном пространстве, поэтому в данном примере они отображаются как [EBP]-4.
Пример стековой памяти
Чтобы проиллюстрировать информацию выше, приведем пример простой программы на языке C, которая вызывает функцию addFunc, складывает два числа (1+4) и выводит результат на экран.
Если сосредоточиться на коде функции addFunc, то в качестве аргументов передаются два параметра (a и b) и локальная переменная c, в которой хранится результат. После компиляции программы ее можно загрузить в x64dbg. Ниже показано, как будет выглядеть ассемблерный код для этой программы:
Первые три строки — это так называемый пролог функции, именно здесь в стеке создается пространство для функции.
push ebp сохраняет ESP (предыдущий указатель стекового кадра), чтобы к нему можно было вернуться в конце функции. Стековый кадр используется для хранения локальных переменных, и каждая функция будет иметь собственный стековый кадр в памяти.
mov ebp, esp перемещает текущую позицию стека в EBP, которая является основанием стека. Теперь у нас есть точка отсчета, которая позволяет ссылаться на наши локальные переменные, хранящиеся в стеке. Значение EBP больше никогда не меняется.
sub esp, 10 увеличивает стек на 16 байт (10 в шестнадцатеричном формате), чтобы выделить место в стеке для любых переменных, на которые нам нужно ссылаться.
Ниже показано, как будет выглядеть стек для этой программы. Каждый используемый фрагмент данных располагается друг над другом на участке памяти в соответствии с приведенной ранее схемой.
EBP-10
EBP-C
EBP-8
EBP-4 (int c)
EBP = Помещается в стек в начале функции. Это начало нашего стекового кадра.
EBP+4 = Адрес возврата к предыдущей функции
EBP+8 = Параметр 1 (int a)
EBP+C = Параметр 2 (int b)
Данный пример иллюстрирует, что в этом стеке выделено место для четырех локальных переменных, однако у нас есть только одна переменная — int c.
mov edx,dword ptr ss:[ebp+8]: здесь мы перемещаем int a (со значением 1) в регистр EDX.
Важной частью здесь является [ebp+8]. Квадратные скобки означают, что вы напрямую обращаетесь к памяти в этом месте. Это ссылка на место в памяти, которое находится на 8 байт выше в стеке, чем то, что находится в EBP.
Ранее мы упоминали, что параметры, перемещаемые в функцию, всегда находятся в более высоком адресном пространстве, которое расположено ниже по стеку. Наши параметры int a и int b были переданы в функцию до создания стекового кадра, поэтому они находятся в ebp+8 и ebp+c.
mov eax,dword ptr ss:[ebp+C]: то же самое, что и выше, но теперь мы ссылаемся на ebp+C, то есть int b (значение 4), и перемещаем его в регистр EAX.
Команда add eax, edx добавляет и сохраняет результат в EAX.
mov dword ptr ss:[ebp-4],eax: здесь мы перемещаем результат, хранящийся в EAX, в локальную переменную int c.
Локальная переменная «c» определяется внутри функции, поэтому она находится в более низком адресе памяти, чем верхняя часть стека. Таким образом, поскольку она находится внутри стекового кадра и имеет размер 4 байта, мы можем просто использовать часть пространства, ранее выделенного для переменных, вычитая 10 из esp, и в этом случае воспользоваться EBP-4.
mov eax,dword ptr ss:[ebp-4]: большинство функций возвращают значение, хранящееся в EAX, поэтому если выше возвращаемое значение находилось в EAX и мы переместили его в переменную «c», то здесь оно просто помещается обратно в EAX, готовое к возврату.
Leave: это маска для операции, которая перемещает EBP обратно в ESP и выводит его из стека, т. е. подготавливает стековый кадр функции, которая вызвала эту функцию.
Команда ret перенаправляет к обратному адресу для возвращения к вызываемой функции, у которой есть хорошо сохранившийся стековый кадр, потому что мы запомнили его в начале этой функции.
Практический пример: стековая память и x64dbg
В предыдущей статье было показано, как распаковать вредоносные программы с помощью x64dbg. Теперь мы рассмотрим некоторые функции, используемые вредоносным ПО, и то, как используется стек.
Сначала откройте распакованную вредоносную программу в x64dbg; в данном примере программа называется просто 267_unpacked.bin.
Перейдите к точке входа вредоносной программы, выбрав Debug («Отладка»), а затем Run («Выполнить»).
Сейчас мы находимся в точке входа вредоносной программы, и я выделил два окна, которые содержат информацию о стековой памяти:
В первом окне показаны параметры, которые были перенесены в стек. Мы знаем, что это параметры, а не переменные, так как это esp+, а не esp-, как объяснялось ранее.
Второе окно — это собственно стековая память:
Первый столбец — это список адресов в стековой памяти. Как упоминалось ранее, высокие адреса находятся внизу, а низкие — вверху.
Второй столбец содержит данные, которые были помещены в стек, а синие скобки представляют отдельные стековые кадры. Помните, что каждая функция будет иметь собственный стековый кадр для хранения своих параметров.
В третьем столбце содержится информация о том, что он автоматически заполняется утилитой x64dbg. В этом примере мы видим адреса, куда x64dbg вернется после выполнения функции.
На изображении ниже первой командой, на которую указывает EIP, является push ebp; текущее значение в EBP, которое выделено на изображении ниже, — 0038FDE8.
Посмотрев на окно стека, мы выделили этот адрес, который является текущим базовым указателем стекового кадра.
При нажатии кнопки Step over («Обойти») EBP помещается в стек, и после завершения этой функции вредоносная программа может вернуться к этому адресу.
Теперь нам нужно переместить наш текущий указатель стека в ESP — это адрес 0038FDDC, выделенный ниже.
Выполнение этой команды перемещает ESP в регистр EBP, который выделен ниже.
Затем вредоносная программа освобождает место в стеке путем вычитания 420 из ESP. Она использует вычитание для создания области в нижнем адресном пространстве, которое находится выше по стеку (на следующем изображении показано нижнее адресное пространство над текущим стековым кадром).
Затем выполнение команды sub esp, 420 обновляет стек.
Обратите внимание, что теперь мы находимся в более низком адресном пространстве, которое находится выше по стеку, а ESP обновлен для отображения нового местоположения на вершине стека.
Это общая схема, которую вы увидите при запуске функций вредоносных программ и с которой вам предстоит познакомиться.
Далее идут три инструкции push, которые перемещают значения трех регистров в стек. Как и ожидалось, пошаговое выполнение данных инструкций обновляет стек и окно параметров:
На следующем этапе рассмотрим одну из функций, написанных хакером, и разберемся, что выполняет функция и как задействуется стек.
На изображении ниже мышь наведена на функцию 267_unpacked.101AEC9, при выполнении которой в x64dbg появляется всплывающее окно с предварительным просмотром данной функции. Это позволяет пользователю увидеть часть ассемблерного кода вызываемой функции. В этом всплывающем окне мы видим, что большое количество строк перемещается в переменные, и мы знаем, что это переменные, благодаря синтаксису ebp-. Такие строки представляют собой обфусцированные API вызовов Windows, которые будут использоваться вредоносным ПО для выполнения различных действий, таких как создание процессов и файлов на диске.
Перейдя к этой функции, мы можем более детально рассмотреть, что происходит, а также увидеть, как стек используется в x64dbg.
В правом нижнем углу выделен созданный стековый кадр, и снова, как и предполагалось, у нас есть пролог функции.
Вход в эту функцию теперь обновляет ESP, который является адресом 0038F9AC в стековой памяти, содержащей адрес возврата к функции main, а также создает пространство в стеке путем вычитания 630 из ESP. Инструкции, начинающиеся с mov, перемещают имена хешированных функций в свои собственные переменные.
Прокручивая вниз ассемблерный код, мы доходим до конца функции и видим несколько вызовов функций, которые используются для деобфускации хешей, только что перенесенных в переменные.
Выделенные команды — это так называемый «эпилог функции», который очищает стек после завершения функции. Мы переходим к этим инструкциям, выбрав интересующую нас инструкцию, «add esp, C», а затем выбрав «Debug» на панели инструментов и «Run until selection».
Это обновляет EIP согласно инструкции, которую мы выделили, а также показывает стек перед очисткой.
В прологе функции для создания пространства в стеке вредоносная программа должна была произвести вычитание из ESP, чтобы иметь возможность выделить место в стеке, которое находилось в нижнем адресном пространстве. Теперь нам нужно удалить выделенное пространство, поэтому, выполнив команду add esp, C, мы добавляем шестнадцатеричное значение «C» в стек, чтобы переместиться вниз в более высокое адресное пространство.
На изображении ниже показан обновленный стек после выполнения команды add esp, C.
Следующая команда — mov esp, ebp, которая переместит значение в EBP в ESP. Наш текущий EBP — 0042F3EC. Прокручивая вниз данные в окне стека, мы видим, что этот адрес содержит наш старый ESP, который является указателем стека.
Выполнение этой команды очищает стек.
Команда pop ebp открывает адрес 00E0CDA8, который хранился в верхней части стека, и перемещает его в EBP.
Это означает, что при выполнении следующей инструкции ret мы вернемся к адресу 00E0CDA8.
На изображении выше показано, что мы вернулись к «основной» функции вредоносного кода и находимся по адресу 00E0CDA8, сразу после функции, которую мы только что проанализировали в x64dbg.
Теперь вы готовы приступить к реверс-инжинирингу вредоносного ПО с помощью x64dbg! В следующей статье мы разберем, как применить знания, полученные в предыдущих статьях блога, чтобы выполнить обратную разработку на практике.
О стеке простыми словами — для студентов и просто начинающих
Привет, я студент второго курса технического университета. После пропуска нескольких пар программирования по состоянию здоровья, я столкнулся с непониманием таких тем, как «Стек» и «Очередь». Путем проб и ошибок, спустя несколько дней, до меня наконец дошло, что это такое и с чем это едят. Чтобы у вас понимание не заняло столько времени, в данной статье я расскажу о том что такое «Стек», каким образом и на каких примерах я понял что это такое. Если вам понравится, я напишу вторую часть, которая будет затрагивать уже такое понятие, как «Очередь»
Теория
На Википедии определение стека звучит так:
Стек (англ. stack — стопка; читается стэк) — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).
Поэтому первое, на чем бы я хотел заострить внимание, это представление стека в виде вещей из жизни. Первой на ум мне пришла интерпретация в виде стопки книг, где верхняя книга — это вершина.
На самом деле стек можно представить в виде стопки любых предметов будь то стопка листов, тетрадей, рубашек и тому подобное, но пример с книгами я думаю будет самым оптимальным.
Итак, из чего же состоит стек.
Стек состоит из ячеек(в примере — это книги), которые представлены в виде структуры, содержащей какие-либо данные и указатель типа данной структуры на следующий элемент.
Сложно? Не беда, давайте разбираться.
На данной картинке схематично изображен стек. Блок вида «Данные/*next» и есть наша ячейка. *next, как мы видим, указывает на следующий элемент, другими словами указатель *next хранит адрес следующей ячейки. Указатель *TOP указывает на вершину стек, то есть хранит её адрес.
С теорией закончили, перейдем к практике.
Практика
Для начала нам нужно создать структуру, которая будет являться нашей «ячейкой»
Новичкам возможно будет не понятно, зачем наш указатель — типа comp, точнее сказать указатель типа структуры comp. Объясню, для того чтобы указатель *next мог хранить структуру comp, ей нужно обозначить тип этой структуры. Другими словами указать, что будет хранить указатель.
После того как у нас задана «Ячейка», перейдем к созданию функций.
Функции
Функция создания «Стека»/добавления элемента в «Стек»
При добавлении элемента у нас возникнет две ситуации:
Разберем чуть чуть по-подробнее.
Во-первых, почему функция принимает **top, то есть указатель на указатель, для того чтобы вам было наиболее понятно, я оставлю рассмотрение этого вопроса на потом. Во-вторых, по-подробнее поговорим о q->next = *top и о том, что же означает ->.
-> означает то, что грубо говоря, мы заходим в нашу структуру и достаем оттуда элемент этой структуры. В строчке q->next = *top мы из нашей ячейки достаем указатель на следующий элемент *next и заменяем его на указатель, который указывает на вершину стека *top. Другими словами мы проводим связь, от нового элемента к вершине стека. Тут ничего сложного, все как с книгами. Новую книгу мы кладем ровно на вершину стопки, то есть проводим связь от новой книги к вершине стопки книг. После этого новая книга автоматически становится вершиной, так как стек не стопка книг, нам нужно указать, что новый элемент — вершина, для этого пишется: *top = q;.
Функция удаления элемента из «Стека» по данным
Данная функция будет удалять элемент из стека, если число Data ячейки(q->Data) будет равна числу, которое мы сами обозначим.
Здесь могут быть такие варианты:
Для лучшего понимания удаления элемента проведем аналогии с уже привычной стопкой книг. Если нам нужно убрать книгу сверху, мы её убираем, а книга под ней становится верхней. Тут то же самое, только в начале мы должны определить, что следующий элемент станет вершиной *top = q->next; и только потом удалить элемент free(q);
Если книга, которую нужно убрать находится между двумя книгами или между книгой и столом, предыдущая книга ляжет на следующую или на стол. Как мы уже поняли, книга у нас-это ячейка, а стол получается это NULL, то есть следующего элемента нет. Получается так же как с книгами, мы обозначаем, что предыдущая ячейка будет связана с последующей prev->next = q->next;, стоит отметить что prev->next может равняться как ячейке, так и нулю, в случае если q->next = NULL, то есть ячейки нет(книга ляжет на стол), после этого мы очищаем ячейку free(q).
Так же стоит отметить, что если не провести данную связь, участок ячеек, который лежит после удаленной ячейки станет недоступным, так как потеряется та самая связь, которая соединяет одну ячейку с другой и данный участок просто затеряется в памяти
Функция вывода данных стека на экран
Самая простая функция:
Здесь я думаю все понятно, хочу сказать лишь то, что q нужно воспринимать как бегунок, он бегает по всем ячейкам от вершины, куда мы его установили вначале: *q = top;, до последнего элемента.
Главная функция
Хорошо, основные функции по работе со стеком мы записали, вызываем.
Посмотрим код:
Вернемся к тому, почему же в функцию мы передавали указатель на указатель вершины. Дело в том, что если бы мы ввели в функцию только указатель на вершину, то «Стек» создавался и изменялся только внутри функции, в главной функции вершина бы как была, так и оставалась NULL. Передавая указатель на указатель мы изменяем вершину *top в главной функции. Получается если функция изменяет стек, нужно передавать в нее вершину указателем на указатель, так у нас было в функции s_push,s_delete_key. В функции s_print «Стек» не должен изменяться, поэтому мы передаем просто указатель на вершину.
Вместо цифр 1,2,3,4,5 можно так-же использовать переменные типа int.
Заключение
Полный код программы:
Так как в стек элементы постоянно добавляются на вершину, выводиться элементы будут в обратном порядке
В заключение хотелось бы поблагодарить за уделенное моей статье время, я очень надеюсь что данный материал помог некоторым начинающим программистам понять, что такое «Стек», как им пользоваться и в дальнейшем у них больше не возникнет проблем. Пишите в комментариях свое мнение, а так же о том, как мне улучшить свои статьи в будущем. Спасибо за внимание.