yet another linux process injection

As you my know there are two methods

1) using LD_PRELOAD, don`t work if you want to inject into already running (and perhaps even many days) process

2) ptrace. Has the following inherent disadvantages

• target process can be ptraced by somebody else
• victim program can detect ptrace
• you just want to avoid in logs something like ptrace attach of "./a.out"[PID] was attempted by "XXX"

So I developed very rough analogs of famous VirtualAllocEx/VirtualProtectEx + simple hook to hijack execution onto assembly written shellcode to call dlopen/dlsym. Currently only x86_64 supported bcs I am too lazy to rewrite this asm stub

Prerequisites
You must have root privileges and be able to build and load kernel modules. I tested code on kernel 6.8, 5.15 and probably it also can work on 4.x, not sure about more old versions

Lets start lighting the dirty details in reverse order

kssp library, part 2

Previous part 

I was struck by the idea of how to reduce size of graph before enumerating all K-th shortest paths. We can use cut-points. By definition if we have cut-point in some shortest path it must be visited always - otherwise you can`t reach the destination. So algo is simple

1. find with Dijkstra algo first shortest paths for whole graph
2. find all cut-points in whole graph
3. iterate over found shortest path - if current vertex is cut-point - we can run brute-force from previous cut-point till current

Results are crazy anyway - on the same test 7

• Yen: 13.86s, 29787, 3501 cycles
• Node Classification: 118.4s, 30013, 3501 cycles
• Postponed Node Classification: 104.95s, 30013, 3501 cycles
  
• PNC*: 120.33s, 30013, 3501 cycles
  
• Parsimonious Sidetrack Based: 4.66s, 29980, 3501 cycles
  
• Parsimonious Sidetrack Based v2: 4.79s, 29980, 3501 cycles
  
• Parsimonious Sidetrack Based v3: 4.85s, 29980, 3501 cycles
  
• Sidetrack Based: 4.18s, 29980, 3501 cycles
  
• Sidetrack Based with update: 4.34s, 29980, 3501 cycles
  

At this time all algos worked to completion and again gave different results...
Source code

kssp library

I`ve tried to solve CSES task "visiting cities"

Looks like you can use kind of brute-force - get 1st shortest paths, then all remained with the same cost and make union of cities in each path - nor elegant nor smart algorithm, just to estimate if this approach works at all

I remember from my university course "graph theory" about Yen`s algo to get K-th shortest path so choosed to use some ready (and hopefully well-tested) implementation - kssp library from INRIA (yep - famous place where OCaml was invented)

And then happened real madness - different algos gave me different result and moreover - they didn't match with "correct" results from CSES! Lets see what I got (all results for test 7, compilation options -O3 -DTIME -DNDEBUG):

• Yen - 470s, 30157 cities
• node classification - 4.37s, 30140 cities
• postponed node classification - 3.83s, 30140 cities
• postponed node classification with star - 3.76s, 30140 cities
• sidetrack based - consumed 13Gb of memory and met with OOM killer
  
• parsimonious sidetrack based - OOM again, perhaps bcs not enough parsimonious :-)
  

Source code

qmake - wtf ?

I tried today build fresh eql from git and got 16815 errors from linker !
After a comparison with the old version I found that qmake generating different Makefile.Release:
< DEFINES       = -DUNICODE -DWIN32 -DQT_LARGEFILE_SUPPORT -DEQL_LIBRARY -DQT_NAMESPACE=QT -DQT_DLL -DQT_NO_DEBUG -DQT_NO_KEYWOR
DS -DQT_XML_LIB -DQT_GUI_LIB -DQT_CORE_LIB -DQT_HAVE_MMX -DQT_HAVE_3DNOW -DQT_HAVE_SSE -DQT_HAVE_MMXEXT -DQT_HAVE_SSE2 -DQT_THRE
AD_SUPPORT
---
> DEFINES       = -DUNICODE -DWIN32 -DQT_LARGEFILE_SUPPORT -DEQL_LIBRARY -DQT_DLL -DQT_NO_DEBUG -DQT_NO_KEYWORDS -DQT_XML_LIB -D
QT_GUI_LIB -DQT_CORE_LIB -DQT_HAVE_MMX -DQT_HAVE_3DNOW -DQT_HAVE_SSE -DQT_HAVE_MMXEXT -DQT_HAVE_SSE2 -DQT_THREAD_SUPPORT

Yes, was used the same version of qmake in both cases
Wtf ?

Update: I found real reason of such behaviour - it`s bcs I forgot add DEFINES     += QT_NAMESPACE=QT to each of eql .pro files. I think this is very annoying and error-prone to fix every .pro file

import graph maker for graphviz

Just small perl script to parse dumpbin /imports output and make .dot file for graphviz

C++ Programming Language (4th Edition) - wtf ?

Publication Date: March 25, 2013

 Extensively rewritten to present the C++11 language

1040 pages. prooflink.
Previous edition also had 1040 pages. I just cannot imagine how it is possibly.

bug in "The Algorithm Design Manual", Second Edition ?

Сitation from subchapter 8.7.2 When are Dynamic Programming Algorithms Efficient? on page 315:

Let LP' [i, j, S] denote the longest simple path from i to j, where the intermediate vertices on this path are exactly those in the subset S. Thus, if S = {a, b, c}, there are exactly six paths
consistent with S: iabcj, iacbj, ibacj, ibcaj, icabj, and icbaj. This state space is at most 2**n, and thus smaller than enumerating the paths

Wait, if this is exponent we must have 2 ** 3 = 8 paths. But actually this is factorial ! Why Skiena claims that this is exponent ?

AVX structure

It seems that AVX has crazy structure. Obvious first step is order on opcode byte. Then for each opcode we need yet 4 tables for pp. Next for 66 prefix we need yet 3 tables for 0f, 0f38 & 0f3a. And anyway we have ambiguity:

• for W field: vmovd - 128.W0 vs vmovq - 128.W1
• for vvvv field: vmovss - NDS.LIG.WIG vs vmovss - LIG.WIG
• for L field: vzeroall - 256.WIG vs vzeroupper - 128.WIG

Wrote simple perl script for instructions parsing and simple ordering

sprintf_s - wtf ?

Lets assume that we set some handler with LdrRegisterDllNotification and just dump all (un)loaded modules to log file. Access to this log is synchronized with critical section - lets name it LogFileCSection. Today I discovered that this simple scheme can lead to unpredictable deadlocks:
thread 1:

02fbd09c 77c88dd4 ntdll_77c50000!ZwWaitForSingleObject+0x15
02fbd100 77c88cb8 ntdll_77c50000!RtlpWaitOnCriticalSection+0x13e
02fbd128 6c4d6144 ntdll_77c50000!RtlEnterCriticalSection+0x150 ; waits on LogFileCSection
02fbd1e0 6c4baf66 xxx!log_with_time+0x22
02fbd210 77cb76b8 xxx!my_notifier+0x36
02fbd240 77c8c74a ntdll_77c50000!LdrpSendDllNotifications+0x45
02fbd328 77c8c389 ntdll_77c50000!LdrpFindOrMapDll+0x735
02fbd4a8 77c8c4b5 ntdll_77c50000!LdrpLoadDll+0x2b2
02fbd4e0 759a1d2a ntdll_77c50000!LdrLoadDll+0xaa ; LdrpLoaderLock acquired
02fbd518 7741493c KERNELBASE!LoadLibraryExW+0x178
02fbd52c 6b268546 KERNEL32!LoadLibraryW+0x11
02fbd540 6b261404 IEFRAME!GetDloadFunction+0x20
02fbd55c 6b261623 IEFRAME!DwmSetWindowAttribute+0x2f
02fbd580 6b2615bd IEFRAME!CTabThumbnailHandler::_OnCreate+0x45
02fbd59c 6b2d7e17 IEFRAME!CTabThumbnailHandler::v_WndProc+0xa0
02fbd5c0 766c62fa IEFRAME!CImpWndProc::s_WndProc+0x65
02fbd5ec 766c6d3a USER32!InternalCallWinProc+0x23
02fbd664 766c6de8 USER32!UserCallWinProcCheckWow+0x109
02fbd6c0 766ca740 USER32!DispatchClientMessage+0xe0
02fbd700 77c6011a USER32!__fnINLPCREATESTRUCT+0x91
02fbd780 766ca8e8 ntdll_77c50000!KiUserCallbackDispatcher+0x2e
02fbda2c 766caa3c USER32!VerNtUserCreateWindowEx+0x1a9
02fbdae0 766c8a5c USER32!_CreateWindowEx+0x210
02fbdb1c 6b293892 USER32!CreateWindowExW+0x33
02fbdb5c 6b24ad22 IEFRAME!Detour_CreateWindowExW+0x6a
02fbdb9c 6b261adb IEFRAME!SHFusionCreateWindowEx+0x47
02fbdcec 6b2619f6 IEFRAME!CTabThumbnailHandler::_Initialize+0xc6
02fbdcfc 6b261118 IEFRAME!CTabThumbnailHandler::CreateInstance+0x3f
02fbdd2c 6b284a68 IEFRAME!CShellBrowser2::AfterWindowCreated+0x9c
02fbfe40 6b294f7a IEFRAME!CTabWindow::_TabWindowThreadProc+0x23c
02fbfef8 76215c2b IEFRAME!LCIETab_ThreadProc+0x2c1
02fbff08 774133ca iertutil!CIsoScope::RegisterThread+0xab
02fbff14 77c89ed2 KERNEL32!BaseThreadInitThunk+0xe


Stupid question

There are some source code/samples for developing of system health agents/validators ?

binary tree for multithread access

Task
I need some binary tree structure for concurrent access from multiple threads where some threads do searching and some other perform insert/delete operations. This structure must work both in kernel and user mode

Solutions
Lets add some sync primitive to each tree node -  it is going to be SRWLock in user mode and EX_PUSH_LOCK in kernel mode. It`s clear that reader can acquire shared lock while writer will use exclusive one. Bcs order of locks always have to be the same - we need tree structure with top-down rebalancing (I hope this is right assumption). So lets see which kinds of trees allow such operations

1. weight-balanced tree. Drawbacks: need to use floating point, so in kernel mode we must care about FPU context saving/restoring
2. classical B-tree. I think there may be a problem with granularity - when node contains a big number of keys and we need to lock it exclusively - all search operations will be blocked from this node till the lowest level of its children
3. red-black tree. Looks like it is a good candidate but sadly I cannot find implementation in plain C with top-down rebalancing :-(

Do I miss something important ?

Dangerously Overinformed

completed quiz

You got 18 of 20 correct.
Yes, I never used Scala & Ada, he-he

scheduling on xp - wtf ?

а вот например я сегодня написал код, проходящий по всяким глубоко внутренним структурам планировщика. Например на моей тестовой xp 32bit показывает примерно такое:

AffinityMask

а вот например windows7 (и соотв-но w2008r2) могут поддерживать более 64 камней
А как известно ф-ция SetThreadAffinityMask в качестве маски имеет аргумент типа DWORD_PTR, что позволяет задать маску ровно для 64 камней. Если же на машине больше - то предлагают использовать всякие ритуальные пляски с бубном типа SetThreadIdealProcessorEx и заданием т.н. processor group.
Предположим (потому что у меня банально нету такого железа) что мы запущены на машине, где больше 64 камней. Количество камней я как-нть из kernel-mode узнать могу (KeNumberProcessors например). Соотв-но дальше я хочу свой поток подключить к каждому имеющемуся камню и достать всякое из KPRCB например. Ясно что я должен использовать кроме subj еще и processor group. А вот дальше непонятно - а сколько таких групп в системе ? А сколько в каждой камней (а системы бывают например на 96 камней - не кратные 64) ? А как можно провернуть такой трюк в kernel mode ?
Кто-нть имел подобный опыт ?

Update: вдумчивое разглядывание msdn подсказывает, что нужные ф-ции называются примерно так:

• SetThreadGroupAffinity
• GetMaximumProcessorGroupCount
• GetLogicalProcessorInformationEx
  

Наверняка все реализовано через какие-нть плохо документированные Information Classes NtQuerySystemInformation

размер KiTimerTableListHead

а вот например вижу я под vista sp2 примерно такой замечательный кусок кода в ф-ции KeSetTimerEx:

  movzx   edi, byte ptr [esi+2] ; KTIMER.Header.Hand
  mov     eax, large fs:20h ; KPCR.Prcb
  mov     ecx, edi
  and     ecx, 1Fh ; KTIMER.Header.Hand & 0x1F
  lea     ebx, [eax+ecx*8+4A0h] ; somewhere inside KPRCB.LockQueue
  mov     ecx, ebx
  call    KeAcquireQueuedSpinLockAtDpcLevel
  mov     byte ptr [esi+3], 0
  mov     eax, [esi+18h]
  mov     ecx, [esi+1Ch]
  cmp     eax, ecx
  mov     [ecx], eax
  mov     [eax+4], ecx
  jnz     short loc_4ABC30
  shl     edi, 4 ; KTIMER.Header.Hand * sizeof(KTIMER_TABLE_ENTRY)
  add     edi, offset _KiTimerTableListHead ; KiTimerTableListHead[KTIMER.Header.Hand]
  cmp     edi, [edi]

Во всех источниках сказано что размер таблицы KiTimerTableListHead под vista равен 512 элементов. Собственно проверить это легко - адрес KiTimerTableListHead 0x4FCB80, адрес следующей за ней структуры AlpcpNPLookasides 0x4FEB80. Размер 0x2000 / 0x10 = 512 элементов. Еще одна проверка - ф-ция KiComputeTimerTableIndex возвращает результат как маску с 0x1FF
В приведенном же коде мы видим что в регистре edi хранится байт, взятый из KTIMER.Header.Hand и используется как индекс в KiTimerTableListHead для проверки всякого. В байте однако число 512 никак не может уместиться. Соотв-но wtf ?

совсем отупел

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

Есличо я в курсе за ф-цию WTSGetActiveConsoleSessionId - это совсем не про то что нужно. Начиная с висты в user32.dll есть также малодокументированная ф-ция _UserTestTokenForInteractive - оно уже больше на правду похоже, но мне и под xp/w2k3 нужно и еще для Terminal Server

crypto lib with avx

а вот скожите мне - есть ли в природе крипто-либы, позволяющие утилизировать AVX ?
я тут давеча собрал botan например - он умеет только ssse3
OpenSSL также имеет для некоторых алгоритмов вставки на asm, но они не первой свежести (2005-2007 годов и в основном под 586 & x86_64, что является весьма размытым понятием в наше время)
неужто все авторы opensource нищеброды никто не озаботился до сих пор поддержкой AVX ?

colobot

а вот например в далеком 2001 году была такая дико угарная игрушка, которая программировалась
И вот полез я давеча в инторнет искать, появилось ли чо-нть с тех пор аналогичное для обучения детей программированию. И вы таки мне не поверите - нифига не нашел (кроме мрачной книжки Land of Lisp. Кому в 21 веке сдались всякие текстовые игры ?)
Неужели и вправду все так грустно ? Ведь угарнейшая тема на самом деле - всякие обучалки программированию в виде программируемых игрушек

Update: грязный хак с применением внешнего скрипта, но вполне рабочий.

idacs

Подумалось в порядке полуночного пьяного бреда: а вот если в IDA Pro встроить какой-нть embedded lisp, то получитца дико хакерский Ъ emacs например, с дизасмом и hex-rays, бгг
Вы таки будете заливисто смеяццо, но биндинг Qt к lispу давно существует

несколько pdb в ida pro

предыдущий псто я удалил чтобы не позоритца
Лучше скажите мне - можно ли в ida pro грузить более одной pdb сразу ?
Нет, я еще с ума окончательно не сошел, если вы вдруг чо-нть не то подумали
Довольно обычным делом бывает ситуация, когда нужно при ковырянии какого-нть драйвера иметь структуры не только из его pdb, но и от ntoskrnl.exe. А иногда еще и от ndis.sys
Спрашивается - как это можно сделать ?