国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

php中的哈希碰撞以及防御

周國輝 / 3215人閱讀

php中的哈希表

php中的變量是以符號表的方式進行存儲的,實際上也是個HashTable,哈希表是通過特定的哈希算法將索引轉換成特定的index然后映射到對應的槽中,然后采用拉鏈法,在一個槽中使用鏈表將數據進行存儲,鏈表的時間復雜度為O(n)。

php中的hashtable的結構定義在Zend/zend_hash.h文件中:

//保存數據的單鏈表結構
typedef struct bucket {
   ulong h;                  /* Used for numeric indexing */
   uint nKeyLength;        //key長度
   void *pData;        //指向bucket中保存的數據的指針
   void *pDataPtr;    //指針數據
   struct bucket *pListNext;    //指向hashtable桶列中下一個元素
   struct bucket *pListLast;    //指向hashtable桶列前一個元素
   struct bucket *pNext;        //指向具有同一個hash index的桶列的后一個元素
   struct bucket *pLast;        //指向具有同一個hash index的桶列的前一個元素
   const char *arKey;        //必須是最后一個成員,key的名稱
} Bucket;

每個數據元素bucket有一個鍵名key,它在整個hashtable中是唯一的,不能重復;根據鍵名可以唯一確定hashtable中的數據元素
在php的數組中,鍵的值可以是整型或字符串,在這里也只有這兩種形式:

如果key為字符串的話:字符串arKey作為鍵名,該字符串的長度為nKeyLength,h字段保存arKey對應的hash值

索引方式: 這時nKeyLength為0,索引值存儲在h上,也就是數據元素的鍵名

bucket是保存在hashtable上的一個雙向鏈表,其向前和向后的元素分別用pLastpNext來表示。新插入的Becket放在該桶的最前面
Bucket中,實際上數據是保存在pData指針指向的內存塊中的,通常這個內存塊是系統額外分配的。但是存在例外,當Bucket保存的數據是一個指針的時候,Hashtable不會另外請求系統分配空間來保存這個指針,而是直接將該指針保存到pDataPtr中,然后再將pData指向本結構成員的地址

hashtable中所有的bucket通過pListNext,pListLast構成了一個雙向鏈表。最新插入的Bucket放在雙向鏈表的最后面

//hashtable結構體
typedef struct _hashtable {
   uint nTableSize;
   uint nTableMask;
   uint nNumOfElements;
   ulong nNextFreeElement;
   Bucket *pInternalPointer;  /* Used for element traversal */
   Bucket *pListHead;
   Bucket *pListTail;
   Bucket **arBuckets;
   dtor_func_t pDestructor;
   zend_bool persistent;
   unsigned char nApplyCount;
   zend_bool bApplyProtection;
#if ZEND_DEBUG
   int inconsistent;
#endif
} HashTable;

hash表的主要保存的數據包括兩部分:哈希表中存儲的數據的個數;保存數據的容器
HashTable結構中,nTableSize指定了HashTable的大小,同時也限定了哈希表中能保存的Bucket的數量,該數值越大,系統為HashTable分配的內存就越多。為了提高計算效率, 系統自動會將nTableSize調整到最小一個不小于nTableSize的2的整數次方,這個其實不太懂
arBucketsHashTable的關鍵,HashTable會自動向系統申請一塊內存,并將其地址賦值給arBuckets,該內存大小正好容納nTableSize指針。我們可以將arBuckets看作一個大小為nTableSize的數組,每個數組元素都是一個指針,用于指向存放數據的Buckets。在初始化的時候每個指針都為null

nTableMask的值永遠是nTableSize - 1,引入這個字段的主要目的是為了提高計算效率,為了快速計算Buckets鍵名在arBuckets數組中的索引

nNumberOfElements記錄了HastTable當前保存的數據元素的個數。當nNumberOfElements大于nTableSize的時候,HashTable就自動擴展為原來的兩倍大小

nNextFreeElement記錄HashTable中下一個可用于插入數據元素的arBuckets索引

pListHead,pListTail分別表示Buckets雙向鏈表的第一個和最后一個元素,這些元素通常是根據插入的順序排列的。也可以根據對應的排序函數對其進行重新排列。pInternalPointer則用于在遍歷HashTable時記錄當前遍歷的位置,它是一個指針,指向當前遍歷到的Bucket,初始值是pListHead

pDestroyctor是一個函數指針,在HashTable的增加,修改,刪除Bucket時自動調用,用于處理相關數據的清理工作

persistent標志位指出了Bucket內存分配的方式。如果persisient為TRUE,則使用操作系統本身的內存分配函數為Bucket分配內存,否則使用PHP的內存分配函數。具體請參考PHP的內存管理。

php中為了使用的哈希算法是DJBX33A

哈希碰撞

php中是使用單鏈表去存儲碰撞的數據的,所以實際上php在哈希表上的平均查找復雜度為O(L),其中L為桶鏈表的平均長度;而最壞的時間復雜度為O(N),此時所以存儲到hashtable上的數據全部發生碰撞,哈希表退化成為單鏈表。

哈希表碰撞就是精心設計的數據使所有的數據發生碰撞。人為的將一個哈希表退化成為一個單鏈表,在哈希表上的各種操作的時間會提升一個數量級,大量消耗CPU,導致系統無法快速響應請求,從而達到拒絕服務(DDOS)的目的

一般情況下很難直接修改php的代碼去制造哈希碰撞攻擊,但是在表單參數$_POST是一個Array,內部就是通過Zend HashTable來實現的,攻擊者只要構造一個含有大量碰撞的key的post請求,就可以達到ddos攻擊的目的

哈希表碰撞的防御

以上說了通過http post請求中的表單數據進行攻擊,防御的方式可以:

在php5.3以上的版本中,post參數的數量存在最大的限制max_input_vars => 1000

在web服務器層面進行處理,如通過限制請求body大小和參數的數量等,這個也是目前使用最多的解決方案

其實以上的兩種解決方案并不能解決問題,因為只是單純的在參數的數量上進行限制了,但是入股請求的數據中包含json數據,但其中的數據就是碰撞的array。理論上,只要php代碼某處構造array的數據依賴于外部輸入,則都可能造成這個問題,因此徹底的解決方案是更改Zend底層的HashTable實現

限制每個桶鏈表的最長長度

使用其他數據結構如紅黑樹取代鏈表組織碰撞哈希(并不解決哈希碰撞,只是減輕攻擊影響,將N個數據的操作時間從O(N^2)降至O(NlogN),代價是普通情況下接近O(1)的操作均變為O(logN))

參考:

php內核探索:http://www.nowamagic.net/libr...

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/22349.html

相關文章

  • 「構建安全的 PHP 應用」讀書筆記

    摘要:書名構建安全的應用作者美譯者張慶龍以下記錄這本安全小書的大致內容,對書中的知識點進行備忘??梢员WC內容的安全性,使得只有最終傳遞到的具有有效證書的接收者才能得到這一內容。缺省安全及跨站攻擊缺省安全我們應該為驗 書名:構建安全的 PHP 應用 作者:(美) Ben Edmunds 譯者:張慶龍 以下記錄這本 PHP Web 安全小書的大致內容,對書中的知識點進行備忘。 不要相信任何用...

    kviccn 評論0 收藏0
  • 系統的講解 - PHP WEB 安全防御

    摘要:支持自動識別密碼哈希格式并通過字典破解密碼哈希。支持枚舉用戶密碼哈希權限角色數據庫數據表和列。支持在數據庫管理系統中搜索指定的數據庫名表名或列名。水平越權用戶未授權可以訪問用戶的數據。對于所有需要權限控制的位置,必須嚴格檢驗用戶權限級別。 常見漏洞 showImg(https://segmentfault.com/img/bVbst5x?w=918&h=921); 看到上圖的漏洞是不是...

    LinkedME2016 評論0 收藏0
  • 幾分鐘理解 數據結構 - 哈希表及其優化

    摘要:小概哈希容器也可以理解為是一種映射容器,采用哈希算法映射算法,散列算法,將不定長的數據壓縮成定長的數據,這串定長值我們稱為哈希值,并將不同的哈希值分組存起來,每一個分組我們認為是一個槽我們將不同的數據格式通過哈希算法,將其映射到不同的槽內, 小概 哈希容器也可以理解為是一種映射容器,采用哈希算法(映射算法,散列算法),將不定長的數據壓縮成定長的數據,這串定長值我們稱為 哈希值,并將不同...

    Dean 評論0 收藏0
  • PHP 數組

    摘要:以下為數組的基礎結構,插入,查找和過程。再存放其,如果根據其下標計算取模得到的中已經有值,那么說明出現了哈希碰撞,這個時候把當前中的值取出來保存到當前,把保存的索引保存在當前,以此類推。 以下為 PHP 數組的基礎結構,插入,查找和 rehash 過程。 基礎結構: struct _zend_array { zend_refcounted_h gc; union { ...

    tracy 評論0 收藏0

發表評論

0條評論

周國輝

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<