Що таке помилка переповнення стека?

Стек (або магазин) – структура даних в програмуванні, що працює за принципом магазина з патронами: останній помещеннний в нього об'єкт, обробляється першим.

Пріработе зі стеком часто доводиться стикатися з двома типовими помилками: переповнення стека і спустошенням стека.

Переповнення стека (stack overflow) – одна з типових помилок при роботі зі стеком, яка полягає у спробі додати в стек елемент, коли пам'ять, відведена для зберігання стека повністю зайнята.

У разі, якщо стек моделюється на базі масиву, добавляемое значення може бути записане за межі відведеного для зберігання стека пам'яті, що призведе до пошкодження інші даних, що обробляються програмою. Це нерідко призводить до важко виявляти помилки типа "псування пам'яті". Тому при реалізації стека на основі масиву необхідно перед кожною операцією додавання елемента перевіряти, чи не переповнений Чи стек.

Якщо стек моделюється на зв'язаному списку, то переповнення стека зазвичай виникає тільки при вичерпанні доступною для програми оперативної пам'яті. У цьому випадку програма завершується з діагностикою "Недостатньо пам'яті".

Причиною переповнення стека зазвичай є зациклення на ділянці програми, де кількість операцій додавання в стек перевищує кількість операцій витягання з стека. Інша причина переповнення стека – занадто велика глибина рекурсивних викликів підпрограм, що може говорити про невдало обраному алгоритмі рішення задачі.

Спустошення стека (stack underflow) – інша типова помилка при роботі зі стеком, яка полягає у спробі витягти значення порожнього стека.

У разі, якщо стек моделюється на базі масиву, то при його спустошенні в якості результату операції може бути повернуто випадкове ("відро") значення з області пам'яті, не відведеній для зберігання стека. Це швидше за все призведе до невірної роботі програми. Крім того, при спробі поповнити стек після його помилкового спустошення, дані можуть бути записані в сторонню область пам'яті, що призведе до тих самих непередбачуваних наслідків, що і переповнення стека.

Якщо стек моделюється на зв'язаному списку, то помилка спустошення стека виражається в спробі звернення за недійсним вказівником. Зазвичай це негайно призводить до завершення програми з діагностикою "захист пам'яті".

Причиною спустошення стеку зазвичай є зациклення на ділянці програми, де кількість операцій витягання з стека перевищує кількість операцій додавання в стек. Інша причина переповнення стека – неузгодженість операцій поповнення та вилучення з стека. Наприклад, якщо підпрограма очікує отримати більше параметрів, ніж їй передається при виклику через стек.

Щоб уникати помилок при роботі зі стеком потрібно дотримуватися двох правил.

1. При реалізації операцій зі стеком завжди перевіряти, чи не призведе витребувані дію до переповнення або спустошення стека. Якщо порушення виявлене, то видавати відповідну діагностику та відмовляти у виконанні операції.

2. При кожній операції використання стека перевіряти успішність її, виконання і в разі виникнення помилки вживати відповідних заходів.

Описані правила безпеки призводять до того, що програмний код виявляється перевантажений перевірками. З цієї причини більш ефективним методом є повідомлення про помилки в роботі зі стеком за допомогою механізму виключень або переривань (наприклад, конструкція try … throw в мові С + +).

Додатково в базі даних Генона:

  • Що таке стек в програмуванні?
  • Для чого використовуються покажчики в програмуванні?

Посилання по темі:

  • cyberforum.ru – реалізація стека на С + + з використанням винятків
  • ru.wikipedia.org – Вікіпедія: Переповнення буфера
  • codenet.ru – розглядається уразливість Windows за рахунок використання переповнення стека
  • sdteam.com – стаття «Переповнення стека»
  • xakep.ru – стаття «Переповнення буфера в стеку», Хакер, № 2, 2003

Category: Медицина і здоров'я

Comments (Прокоментуй!)

There are no comments yet. Why not be the first to speak your mind.

Leave a Reply