text:
Thursday, November 15, 2012

FltCreateSectionForDataScan

Thanks everyone for your suggestions. I really appreciate you took the time and sent me emails. Some of the topics you've suggested I won't be able to address for various reasons (mostly having to do with the legal implications of my doing that). However, I have a couple of topics that I might go over in the next couple of months. Incidentally, I also plan to change the frequency of my posts because of changes around my work so I'll probably update the blog whenever I get around to it. I still plan to answer questions though so feel free to leave comments and suggest topics (preferably in email). And now let's proceed to the topic at hand.

Someone suggested it would be useful to take a closer look at what FltCreateSectionForDataScan does and discuss how the same functionality could be achieved in previous OS releases. The FltCreateSectionForDataScan function is documented as being supported only in Win8+ but looking at the documentation page for the FltRegisterForDataScan function there is a mention about the FsRtlCreateSectionForDataScan function, which is documented as being available since Win 2000 SP4 and XPSP2, basically from the time FltMgr is available. A quick look in the debugger at FltCreateSectionForDataScan shows that it's really a wrapper around FsRtlCreateSectionForDataScan so I thought it might be useful to take a closer look at that:

1. As one might expect the FsRtlCreateSectionForDataScan function begins with various parameter checks, primarily to filter out various invalid parameters. There is also a check to see if the FileObject supports sections.
2. The next step is to set the TopLevelIrp to the value 1, which maps to FSRTL_FSP_TOP_LEVEL_IRP.
3. Once that is done there is a call to nt!FsRtlAcquireFileExclusiveCommon. This function is not documented anywhere and I could only find some references in crash dumps. However, looking for just FsRtlAcquireFileExclusive returns more hits and we can see that FsRtlAcquireFileExclusive doesn't do much beyond calling nt!FsRtlAcquireFileExclusiveCommon. In the ntifs.h file we see a comment to the effect that FsRtlAcquireFileExclusive is called from NtCreateSection to avoid deadlocks with file systems, so we can guess that this the same thing going on here. We can also guess that whatever FsRtlCreateSectionForDataScan does is probably pretty similar to NtCreateSection.
4. The next step is to get the file size. This is done by a call to nt!FsRtlGetFileSize, and the documentation for FsRtlGetFileSize states that "If you already own file system resources, you should call FsRtlGetFileSize instead of ZwQueryInformationFile, because attempting to acquire the file object lock would violate locking order and lead to deadlocks. The ZwQueryInformationFile function should be only if you do not already own file system resources.". This makes sense since the function has already acquired the file object lock in the previous step.
5. There is a quick check to see if the file is empty and the function should return with STATUS_END_OF_FILE.
6. Then, once everything is set up we have a call to nt!MmCreateSection. Calling this function directly is not supported by Microsoft and there is no documentation for how to do that. This is basically why FsRtlCreateSectionForDataScan was added. This can be inferred from the msdn page "Installing the Filter Manager rollup package for Windows XP SP2". If the function returns STATUS_FILE_LOCK_CONFLICT the call to nt!MmCreateSection is retried after delaying the thread by nt!FsRtlHalfSecond (I had no idea this existed, but I plan to use it from now on :)).
7. Once the section is created there is a call to nt!CcZeroEndOfLastPage. I've not been able to find any documentation for this function (though it's pretty obvious what it does) except in the NT Insider article "Cache Me if You Can: Using the NT Cache Manager".
8. Once this is done the function releases the locks so the rest of the function is done outside the critical region (that was set up around step 2).
9. The only interesting thing happening in the rest of the function is the creation of the handle for the section in the current process handle table. The rest of it just deals with cleanup and the return path from the function.

One thing to note is that FsRtlCreateSectionForDataScan just creates the section. There are A LOT of FltMgr functions related to these data sections and based on the names most of them are dealing with conflict resolution. I'm not sure what that's about yet and I haven't actually used them anywhere but if you plan to use this API directly in downlevel OSes then you should probably expect some sort of conflicts. Good luck!

Thursday, October 4, 2012

Suggestions

Hi everyone. It seems lately I'm having a hard time coming up with good topics, so I wanted to ask you to send me emails with topics you might be interested in. These could be things you already know but you think might be beneficial to have posted somewhere to the rest of the community or things you're not sure about. However, please keep the requests specific. Things like "minifilter interaction with the memory manager" are simply too vague to be helful. You could ask about specific functions or behaviors or structure members (but again, please keep it specific). You can find my email address on my contact information on this blog.

Thanks,
Alex.

Thursday, September 27, 2012

A Helpful Debugging Technique: Debug Stream Contexts

In this post I'd like to discuss a debugging technique that I found pretty useful. I'm a big fan of keeping lots of information around in debug builds and ASSERTing all over the place. I try to be very careful about what information I keep so that I don't change the actual flow of execution for the code. For example, I tend to try to not add references when I copy some pointers because I don't want to alter when freeing the memory happens for the objects I'm tracking (but this approach requires extra care when asserting since I don't want to use pointers to free memory).
One particularly useful thing I like is to keep track of all the files I've processed in my filter and remember various decisions I made about them and keep back-pointers to things that would otherwise be impossible to find (for example when I base my decision on some parameters in the FLT_CALLBACK_DATA I might take a snapshot of those parameters; or I might keep a stack trace for certain operations and so on). The problem that arises with this approach is, of course, where to store this information. In some cases it's feasible to use some of the structures I'm already using (StreamContext or StreamHandleContext) and just add extra members in debug builds. However, there are other times where this becomes a significant pain and it would alter the filter quite a bit (for example, if the logic of the filter is to check for presence of a context to decide on what to do with a file then adding a context in which I only populate the debugging information for files I don't intend to process would change that logic). Also, certain contexts might store data that isn't fixed in size (like a file name or path) which I typically set to be the last thing in the context so adding more debugging information (which might itself be dynamic in size) would make things very complicated.
The ideal approach would be to set more than one context on an object, but FltMgr's functions don’t really allow that. Well, here is where the some FsRtl functions really come in handy. There is support built in the file system library (FsRtl code) for contexts (which I've discussed in more detail in my post on Contexts in legacy filters and FSRTL_ADVANCED_FCB_HEADER) and the library supports setting multiple contexts for the same stream, with different keys. Moreover, the contexts have two keys and there are pretty cool searching semantics that allow searching on only one key. The functions that deal with this are FsRtlInitPerStreamContext, FsRtlInsertPerStreamContext and FsRtlLookupPerStreamContext. They’re pretty easy to use and there is even a page on MSDN on Creating and Using Per-Stream Context Structures.
Here is some code that shows how to use these functions:
typedef struct _MY_DEBUG_CONTEXT {

//
// this is the header for the perStream context structure.
//

FSRTL_PER_STREAM_CONTEXT PerStreamContext;

//
// this is the information we want to track.
//

BOOLEAN Flag;

} MY_DEBUG_CONTEXT, *PMY_DEBUG_CONTEXT;

VOID
FreeDebugContext(
__in PVOID ContextToFree
)
{

//
// here we would release and uninitialize any other data..
//

//
// and then we free the actual context.
//

ExFreePoolWithTag( ContextToFree, 'CgbD' );
}

NTSTATUS
SetDebugContext(
__in PFILE_OBJECT FileObject,
__in PVOID Key1,
__in_opt PVOID Key2,
__in BOOLEAN Flag
)
{
PMY_DEBUG_CONTEXT context = NULL;
NTSTATUS status = STATUS_SUCCESS;

__try {

//
// allocate and initialize the context.
//

context = ExAllocatePoolWithTag( PagedPool,
sizeof(MY_DEBUG_CONTEXT),
'CgbD' );

if (context == NULL) {

status = STATUS_INSUFFICIENT_RESOURCES;
__leave;
}

FsRtlInitPerStreamContext( &context->PerStreamContext,
Key1,
Key2,
FreeDebugContext );

//
// initialize all the members that we want to track.
//

context->Flag = Flag;

//
// try to set the context.
//

status = FsRtlInsertPerStreamContext( FsRtlGetPerStreamContextPointer(FileObject),
&context->PerStreamContext );

NT_ASSERT(status == STATUS_SUCCESS);

} __finally {

if (!NT_SUCCESS(status)) {

if (context != NULL) {

ExFreePoolWithTag( context, 'CgbD' );
}
}
}

return status;
}

BOOLEAN
GetDebugContextFlag(
__in PFILE_OBJECT FileObject,
__in PVOID Key1,
__in_opt PVOID Key2
)
{
PMY_DEBUG_CONTEXT context = NULL;

context = (PMY_DEBUG_CONTEXT)FsRtlLookupPerStreamContext( FsRtlGetPerStreamContextPointer(FileObject),
Key1,
Key2 );

if ((context != NULL) &&
(context->Flag)) {

return TRUE;
}

return FALSE;
}

Finally, one more thing to show is how easy it is to find this structure in the debugger:
0: kd> dt @@(tempFileObject) nt!_FILE_OBJECT FsContext  <- get the FsContext
+0x00c FsContext : 0xa24d05f8 Void
0: kd> dt 0xa24d05f8 nt!_FSRTL_ADVANCED_FCB_HEADER FilterContexts. <- look at the FilterContexts  in the FsContext
+0x02c FilterContexts  :  [ 0xa25a1108 - 0x936e93e4 ]
+0x000 Flink           : 0xa25a1108 _LIST_ENTRY [ 0x936e93e4 - 0xa24d0624 ]
+0x004 Blink           : 0x936e93e4 _LIST_ENTRY [ 0xa24d0624 - 0xa25a1108 ]
0: kd> dl 0xa25a1108 <- look at all the entries in the list
a25a1108  936e93e4 a24d0624 9441eb40 92e3cb40
936e93e4  a24d0624 a25a1108 93437438 a24d05f8
a24d0624  a25a1108 936e93e4 00000000 a24d05f4
0: kd> !pool a25a1108 2  <- check the pool type for the first one
Pool page a25a1108 region is Paged pool
*a25a1100 size:   20 previous size:  100  (Allocated) *DbgC  <- this is our structure
Owning component : Unknown (update pooltag.txt)
0: kd> !pool 936e93e4  2   <- for fun, let's see what the other context is
Pool page 936e93e4 region is Nonpaged pool
*936e93d8 size:   68 previous size:    8  (Allocated) *FMsl
Pooltag FMsl : STREAM_LIST_CTRL structure, Binary : fltmgr.sys  <- obviously FltMgr's context
0: kd> dt a25a1108 _MY_DEBUG_CONTEXT  <- display the debugging context
PassThrough!_MY_DEBUG_CONTEXT
+0x000 PerStreamContext : _FSRTL_PER_STREAM_CONTEXT
+0x014 Flag             : 0x1 ''

Thursday, September 20, 2012

Volume Mount Points, Directory Junctions and STATUS_ACCESS_VIOLATION

Hi everyone. I've just spent a couple of days debugging an issue that I think is pretty interesting and I hope publishing this post might save someone a lot of pain.
Before I go into the specifics, let me explain a bit about my setup. My filter opens files for its own use but on behalf of the user (in other words it opens files in response to certain user actions, but the user must have access to the files as well (which is different from certain kinds of filters where the filter uses files but there is no connection between the user and the files; in those cases the files are similar to file system metadata)). It does this by calling FltCreateFile and it uses OBJ_FORCE_ACCESS_CHECK to make sure that all the access checks are performed. The files that the filter opens depend on the file that the user opens and so it's possible that the filter ends up opening symlinks or volume mount points and such. In these cases the file system will return a STATUS_REPARSE and the create will be retried on a different path; the same can happen if a file system filter returns STATUS_REPARSE. If the new path happens to be located on a different volume (which is usually the case with volume mount points, though not always since one can in fact create a mountpoint for C:\ at C:\mnt for example…) then the FltCreateFile call will generally fail with STATUS_MOUNT_POINT_NOT_RESOLVED. I've discussed this at great length in my post on Reparsing to a Different Volume in Win7 and Win8.
The problem I was running into was that when my filter tried to open a path containing a volume mount point it would fail with STATUS_ACCESS_DENIED. This behavior was different from symlinks where the call to FltCreateFile still failed with STATUS_MOUNT_POINT_NOT_RESOLVED. This was something I wanted to investigate since the STATUS_ACCESS_VIOLATION status is one I've learned to pay attention to because it generaly indicates a bug in my code. I thought that maybe I was calling FltCreateFile with some parameter that wasn't set up correctly which led to NTFS or the IO manager or the Object manager to try an invalid access, which was probably trapped in some exception handler and returned to the caller. This was definitely worth fixing since such problems can be exploited.
So I started the looong process of debugging this issue. Being an access violation I figured it comes from some improper memory access, which is different from calling some function that returns an error, because most instructions perform memory accesses so my usual approach of stepping to the next call and walking over it to see the return status would not work. Moreover, I had no guarantee that if I set a breakpoint later on I will actually hit it since any of the memory accesses up to that breakpoint could in fact be the culprit. And, to make things worse, this was in the create path for the file system, which is heavily exercised on a running system, which means that any breakpoint that I set in the debugger that's not threaded will often trigger when another thread happens to try to do a create. Anyway, to spare you the gory details, I eventually found the problem and this is what the stack looked like when the instruction I was about to execute was the one that triggered the access violation:
0: kd> kbn L0xa
# ChildEBP RetAddr  Args to Child
00 b0583190 82a8f20f 92637001 92637001 b0583734 nt!ObpCaptureObjectCreateInformation+0x61
01 b05831dc 82ae2587 b0583734 924d6f78 92637001 nt!ObOpenObjectByName+0x9b
02 b0583338 82ae17f6 b0583734 00120089 92637001 nt!IopFastQueryNetworkAttributes+0x127
03 b05833a4 82a88936 92637001 dc6a18a4 b0583550 nt!IopQueryNetworkAttributes+0x40
04 b0583480 82a6926b 938e34d8 974d6f78 92637008 nt!IopParseDevice+0x115e
05 b05834fc 82a8f2d9 00000000 b0583550 00000640 nt!ObpLookupObjectName+0x4fa
06 b0583558 82a8762b b0583734 924d6f78 00010000 nt!ObOpenObjectByName+0x165
07 b05835d4 82abee29 b058371c 00120089 b0583734 nt!IopCreateFile+0x673
08 b0583630 96297b62 b058371c 00120089 b0583734 nt!IoCreateFileEx+0x9e
09 b05836bc 9631f8f1 92ed7008 938fd008 b058371c fltmgr!FltCreateFileEx2+0xba
0: kd> u
nt!ObpCaptureObjectCreateInformation+0x61:
82a78339 8a01            mov     al,byte ptr [ecx]
82a7833b 833b18          cmp     dword ptr [ebx],18h
0: kd> r
eax=7fff0000 ebx=b0583734 ecx=7fff0000 edx=00000000 esi=00000000 edi=9260dd94
eip=82a78339 esp=b0583154 ebp=b0583190 iopl=0         ov up ei pl nz na po nc
cs=0008  ss=0010  ds=0023  es=0023  fs=0030  gs=0000             efl=00000a02
nt!ObpCaptureObjectCreateInformation+0x61:
82a78339 8a01            mov     al,byte ptr [ecx]          ds:0023:7fff0000=??

So as you can see we 're trying to read one byte from ECX, which is set to 0x7fff0000. Since we're in kernel mode this will fail with access violation. Let's look a bit up the stack to see where that weird ECX value came from (and I added a couple instructions on the bottom just to get the full picture):
0: kd> ub . L0xE
nt!ObpCaptureObjectCreateInformation+0x35:
82a7830c 807d0800        cmp     byte ptr [ebp+8],0    <- compare a parameter to the function with 0.
82a78310 7429            je      nt!ObpCaptureObjectCreateInformation+0x63 (82a7833b) <- and jump if it's 0
82a78312 64a124010000    mov     eax,dword ptr fs:[00000124h] <- look at some address
82a78318 80b83a01000000  cmp     byte ptr [eax+13Ah],0 <- and see if another byte is 0
82a7831f 741a            je      nt!ObpCaptureObjectCreateInformation+0x63 (82a7833b) <- and if that is 0 jump to the same place as above (so we're probably exiting an IF statement)
82a78321 8bcb            mov     ecx,ebx
82a78323 f6c303          test    bl,3 <- check if any of the least significant two bits in ebx are set
82a78326 7406            je      nt!ObpCaptureObjectCreateInformation+0x56 (82a7832e)
82a78328 e8281f0d00      call    nt!ExRaiseDatatypeMisalignment (82b4a255) <- and if they're set then raise an exception for data misalignment
82a7832d cc              int     3 <- and look, there's a breakpoint
82a78333 3bd8            cmp     ebx,eax <- and compare it with EBX
82a78335 7202            jb      nt!ObpCaptureObjectCreateInformation+0x61 (82a78339) <- and exit the IF statement if EBX is smaller than MmUserProbeAddress
82a78337 8bc8            mov     ecx,eax <-move MmUserProbeAddress into ECX
82a78339 8a01            mov     al,byte ptr [ecx] <- and try to read a byte from it.
82a7833b 833b18          cmp     dword ptr [ebx],18h
829b071c  7fff0000
Before I explain what's going on let's see what the IF is actually checking:
0: kd> dp fs:[00000124h] L1
0030:00000124  926bfd48
0: kd> !pool 926bfd48 2
Pool page 926bfd48 region is Nonpaged pool
*926bfd18 size:  2e8 previous size:   10  (Allocated) *Thre (Protected)   <- this is a thread!
Pooltag Thre : Thread objects, Binary : nt!ps
+0x010 CycleTime        : Uint8B
...
+0x13a PreviousMode     : Char   <-and at offset 0x13A we have the PreviousMode !
...

Let's piece it all together. This piece of code is trying to figure out if a buffer that it receives as a parameter (I didn't show that code but that's what's in EBX) is accessible. It first looks at some boolean parameter and if that's TRUE then it looks at the PreviousMode and if that's UserMode then it checks the buffer for alignment (and it raises an exception if it's not aligned) and then it checks it's in user mode memory range ( smaller than MmUserProbeAddress ). If it's not smaller than MmUserProbeAddress then it just does a probe at MmUserProbeAddress. The buffer in question is the _OBJECT_ATTRIBUTES structure, which is actually the same one as the one I pass in for the original create. This is interesting because ObOpenObjectByName can be seen twice on the stack, with the same _OBJECT_ATTRIBUTES parameter, but the first time the call to nt!ObpCaptureObjectCreateInformation works when checking the buffer and the second time it doesn't. Since the PreviousMode is UserMode in both cases, the only difference is that the boolean parameter that ObpCaptureObjectCreateInformation is called with is 1 in the first case and 0 in the second case. This parameter seems to be related to OBJ_FORCE_ACCESS_CHECK since if I don't use OBJ_FORCE_ACCESS_CHECK then the parameter is 1 in both cases and no access violation happens.
One additional thing I'd like to explain is why this check happens only for volume mount points and not symlinks. Volume mount points are different from symlinks in that there before a new IRP_MJ_CREATE is sent to the new path, for volume mount points the IO manager checks whether the user has access to the target volume. The same thing happens for directory junctions, which are similar in implementation to volume mount points. Symlinks don't perform this check and instead the new IRP_MJ_CREATE is simply issued to the new path and access checks will be performed there. Now, for volume mount points this access check takes the form of a IopQueryNetworkAttributes, which in turn is implemented as a special kind of OPEN operation (hence the call to ObOpenObjectByName). It's this second open where ObpCaptureObjectCreateInformation fails and the access violation happens.
This problem was fixed in Win8 and it was very likely a windows bug.
Before I end this post I'd like to summarize some of the things I've discussed:
• There is a windows 7 bug where if FltCreateFile tries to open a path that traverses a volume mount point or directory junction the call will fail with STATUS_ACCESS_VIOLATION. Fixed in Win8.
• This happens because of the extra access checking for volume mount points and directory junctions.
• This doesn't happen for symlinks.
• Workaround: I can't think of anything a filter could do but one posibility to address this problem is to ask customers to not use volume mount points and instead use directory symlinks.
Finally, in closing I'd like to show some code (a modification of the PassThrough sample) that calls FltCreateFile whenever the user tries to open anything that has the name "mnt" (file or folder). After the FltCreateFile call the minifilter breaks so that I get a chance to look at the status returned by the FltCreateFile. Here is the code:

NTSTATUS status;

UNREFERENCED_PARAMETER( FltObjects );
UNREFERENCED_PARAMETER( CompletionContext );

PT_DBG_PRINT( PTDBG_TRACE_ROUTINES,
("PassThrough!PtPreOperationPassThrough: Entered\n") );

if (Data->Iopb->MajorFunction == IRP_MJ_CREATE) {

UNICODE_STRING myFile = RTL_CONSTANT_STRING( L"mnt" );
OBJECT_ATTRIBUTES fileAttributes;
HANDLE fileHandle = NULL;
IO_STATUS_BLOCK ioStatus;
PFLT_FILE_NAME_INFORMATION fileName = NULL;

NTSTATUS ecpFindStatus;
ULONG targetEcpSize = 0;

__try {

//
// this is a preCreate, get the name.
//

status = FltGetFileNameInformation( Data,
FLT_FILE_NAME_OPENED | FLT_FILE_NAME_QUERY_DEFAULT,
&fileName );
if (!NT_SUCCESS(status)) {

DbgBreakPoint();
__leave;
}

//
// we need to parse the name to get the final component
//

status = FltParseFileNameInformation( fileName );

if (!NT_SUCCESS(status)) {

DbgBreakPoint();
__leave;
}

//
//  Compare to see if this is a file we care about.
//

if (!RtlEqualUnicodeString( &fileName->FinalComponent,
&myFile,
TRUE )) {

__leave;
}

//
// intialize the attributes and issue the create.
//

InitializeObjectAttributes( &fileAttributes,
&fileName->Name,
OBJ_KERNEL_HANDLE | OBJ_FORCE_ACCESS_CHECK,
NULL,
NULL );

status = FltCreateFileEx2( FltObjects->Filter,
FltObjects->Instance,
&fileHandle,
NULL,
&fileAttributes,
&ioStatus,
NULL,
FILE_ATTRIBUTE_NORMAL,
FILE_OPEN,
NULL,
0,
0,
NULL );

DbgBreakPoint();
} __finally {

if (fileName != NULL) {

FltReleaseFileNameInformation( fileName );
}

if (fileHandle != NULL) {

ZwClose(fileHandle);
}
}
}

//
//  See if this is an operation we would like the operation status
//  for.  If so request it.
//
//  NOTE: most filters do NOT need to do this.  You only need to make
//        this call if, for example, you need to know if the oplock was
//        actually granted.
//

if (PtDoRequestOperationStatus( Data )) {

status = FltRequestOperationStatusCallback( Data,
PtOperationStatusCallback,
(PVOID)(++OperationStatusCtx) );
if (!NT_SUCCESS(status)) {

PT_DBG_PRINT( PTDBG_TRACE_OPERATION_STATUS,
("PassThrough!PtPreOperationPassThrough: FltRequestOperationStatusCallback Failed, status=%08x\n",
status) );
}
}

Thursday, September 13, 2012

Interesting article

I'm pretty swamped at work so I won't post anything this week, but I'd like to share an article that I found interesting. It's about some malware, Backdoor.Proxybox, that hooks NTFS directly. This is the page on Symantec's blog: Backdoor.Proxybox: Kernel File System Hooking.

Thursday, September 6, 2012

Completing Information Queries in File System Filters

Completing IRP_MJ_QUERY_INFORMATION requests isn't a terribly difficult task but I wanted to discuss some of the basics as well as share some code to show how a minifilter might go about doing this. I've already discussed some of the more advanced topics related to this in my previous posts on Filters And IRP_MJ_QUERY_INFORMATION and on Setting IoStatus.Information.

There are many information classes and many of them can be found on the documentation page for the ZwQueryInformationFile function, though the complete list is documented on the 2.4 File Information Classes page in the MS_FSCC document. Please note that not all of them can be used with IRP_MJ_QUERY_INFORMATION. However, for this post I'll only be focusing on those that can.

Pretty much each information class has an associated structure. For example, the information class of FileAlignmentInformation has the associated FILE_ALIGNMENT_INFORMATION structure. Some of these structures have a fixed size so in that case all a filter has to do is to populate the information and complete the request:

        switch ( Data->Iopb->Parameters.QueryFileInformation.FileInformationClass ) {

case FilePositionInformation:
{
PFILE_POSITION_INFORMATION positionInfo = Data->Iopb->Parameters.QueryFileInformation.InfoBuffer;

// retrieve the current position from the file object

positionInfo->CurrentByteOffset = FltObjects->FileObject->CurrentByteOffset;

// then complete the operation

Data->IoStatus.Status = STATUS_SUCCESS;
Data->IoStatus.Information = sizeof(positionInfo->CurrentByteOffset);
callbackStatus = FLT_PREOP_COMPLETE;
}
break;
....
}
...
return callbackStatus;

The filter can expect that a buffer of the appropriate size is received, otherwise the IO manager will reject the operation with STATUS_INFO_LENGTH_MISMATCH. This is done inside the IO manager, where the IO manager has an array of minimum sizes for each information class (can be seen in the debugger as nt!IopQueryOperationLength) and if the size is smaller than that then the request will fail with the error code I mentioned:

0: kd> u nt!NtQueryInformationFile+0x36 L0xB
nt!NtQueryInformationFile+0x36:
82aa87dc 8b4518          mov     eax,dword ptr [ebp+18h]
82aa87df 83f838          cmp     eax,38h
82aa87e2 7377            jae     nt!NtQueryInformationFile+0xb5 (82aa885b)
82aa87e4 8a80d4a0a782    mov     al,byte ptr nt!IopQueryOperationLength (82a7a0d4)[eax]
82aa87ea 84c0            test    al,al
82aa87ec 746d            je      nt!NtQueryInformationFile+0xb5 (82aa885b)
82aa87ee 0fb6c0          movzx   eax,al
82aa87f1 394514          cmp     dword ptr [ebp+14h],eax
82aa87f4 730a            jae     nt!NtQueryInformationFile+0x5a (82aa8800)
82aa87f6 b8040000c0      mov     eax,0C0000004h
82aa87fb e98e080000      jmp     nt!NtQueryInformationFile+0x8e3 (82aa908e)

Now, there are certain information classes that have variable length. In general this happens with classes that contain names (for example, FileNameInformation) or that return certain lists (like FileStreamInformation that returns all the alternate data streams for the file). In these cases it's impossible for the IO manager to know what the required size might be without querying the file system and so file systems and file system filters will receive requests with what is possibly an insufficient buffer size (there are apps that allocate huge buffer just to avoid reissuing a request, but there are many callers that don't do that; I generally prefer to issue a request with enough buffer in cases where that's possible, for example most files don't have Alternate Data Streams so it's possible to calculate the size of the buffer). Those requests will be failed by the file system (or filter) with the STATUS_BUFFER_OVERFLOW status (which is actually a warning, not an error!). However, different information classes have different requirements about how the structure has to be populated in such cases. There are some structures (like FILE_NAME_INFORMATION) that have a field where the caller can fill in the required size so that the caller can just allocate a buffer of the appropriate size and resend the request. Other structures don't have any such field (like FILE_STREAM_INFORMATION) and so any caller must simply increase the size of the buffer without knowing in advance if it will be sufficient (I personally double the size of the buffer for each iteration but there are other ways of doing it) and then they must issue the request and see whether it was enough.

Finally, there are certain requirements for each information class about how to fill in the buffer even in the event when the request is going to be failed with STATUS_BUFFER_OVERFLOW. For example, for FileNameInformation the buffer must be filled with as many characters as will fit the buffer whereas the FILE_STREAM_INFORMATION must be filled only with complete records. These type of requirements make it necessary for whoever completes the request to be able to specify how much of the buffer actually contains real information. This can be achieved by setting the IoStatus.Information member to the number of bytes to return the caller. The IO manager will then copy the specified number of bytes to the caller's buffer. It is very important to get this right because returning a larger number here will result in the IO manager copying more bytes than were actually written by the file system or filter and is a security problem. For more details on this see Doron's post on How to return the number of bytes required for a subsequent operation. Of course, the specifics of how the buffer must be set up for each class are documented in the pages for each information class or associated structure, so whenever dealing with this subject make sure to re-read those pages and pay great attention to the details.

I wanted to show some more code on how to do this, but there is plenty of code that shows how this is done in the file system sources that come with the WDK. I found the CDFS sources to be a bit more clear for this specific topic, where CdCommonQueryInfo pretty much does it all and shows exactly how to set things for most information classes. FastFat can be a bit more convoluted at times.

Finally, I want to say that whenever I have to deal with this I find it extremely useful to just use FileTest and then query the information class I want while supplying different sized buffers (starting with 1 byte, then 2 bytes and so on) and make sure that I understand exactly what the file system returns without my filter present and how things look with the filter installed.

Thursday, August 30, 2012

Mount Point Resolution with FltGetFileNameInformation - Part II

In the previous post I showed a couple of examples of how FltMgr handles mount point resolution. I also ran into a problem where querying for the normalized name during preCreate for a path that would traverse a mountpoint failed, and I promised I would investigate and post my findings. In this post I will explain what I found and how I went about it (which might be interesting for someone that doesn't have a lot of experience debugging the workings of fltmgr or other kernel components).
So first, let me explain my findings. As a quick refresher, FltMgr performs name normalization by taking an opened name for a file (like C:\foo~1\bar~2.txt) and opening the parent directory (C:\foo~1) and then querying the directory (via the directory enumeration call) for the file name (bar~2.txt). FltMgr uses one of the directory structures that returns the long name for the file (like FILE_BOTH_DIR_INFORMATION or FILE_NAMES_INFORMATION) and then copies the long name for the file (let's say it is BarBarBar.txt). It then does the same for current directory name (for C:\foo~1 it would open C:\ and query for foo~1 and get back FooFooFoo) and then assembles everything back together into C:\FooFooFoo\BarBarBar.txt. Now, this process will fail with STATUS_NOT_SAME_DEVICE if when trying to open a parent directory (C:\foo~1) FltMgr encounters a reparse point that reparses to a different volume. The relevant code is this:
0: kd> u fltmgr!FltpExpandFilePathWorker+0x29e
fltmgr!FltpExpandFilePathWorker+0x29e:
96034a1c ff154c030296    call    dword ptr [fltmgr!_imp__IoGetAttachedDevice (9602034c)]
96034a22 ff765c          push    dword ptr [esi+5Ch]
96034a25 8bf8            mov     edi,eax
96034a27 ff1548010296    call    dword ptr [fltmgr!_imp__IoGetRelatedDeviceObject (96020148)]
96034a2d 3bc7            cmp     eax,edi
96034a2f 740c            je      fltmgr!FltpExpandFilePathWorker+0x2bf (96034a3d)
96034a31 c74508d40000c0  mov     dword ptr [ebp+8],0C00000D4h
96034a38 e9e8feffff      jmp     fltmgr!FltpExpandFilePathWorker+0x1a7 (96034925)

As you can see, FltMgr compares two devices, the one on which the IRP_MJ_CREATE to open the parent directory was issued and the one where it was actually opened on, and if they don't match it will fail with STATUS_NOT_SAME_DEVICE (which is an interesting and confusing choice since the actual error message (from ntstatus.h) is "The target file of a rename request is located on a different device than the source of the rename request." and there is no rename involved). There are a couple of interesting points to make:
• This should only impact preCreate queries since after the IRP_MJ_CREATE completes successfully we are on the final volume and so the opened file name can't traverse any reparse points (as discussed in my previous post on this subject). So in postCreate (and this implies a successful create) there will be no reparse points to traverse.
• The other interesting thing to note is that FltMgr actually issues its IRP_MJ_CREATE violating the file system filter layering rules, in that it sends the request to the top of the IO stack. It does this with the explicit goal of being able to survive reparses to other volumes (like I've discussed elsewhere on this blog). However, it then checks to figure out if it actually ended up on a different volume and fails the operation, which would have happened anyway if they targeted the IRP_MJ_CREATE properly. The only case where this might actually work and the proper layering of the IRP_MJ_CREATE would have failed is where there multiple reparses that eventually end up on the original volume where the IRP_MJ_CREATE was issued on (so you'd have C:\foo~1 reparse to D:\bar~1 which would in turn reparse back to C:\baz~1). This would fail with proper layering of the IRP_MJ_CREATE because the first reparse (from C:\ to D:\) would fail, but it would work with the current implementation because the request is targeted at C:\ and the directory that is opened eventually is on C:\ as well). However, I doubt that this behavior is what FltMgr's designers had in mind and instead I tend to believe that violating the layering in this case was unnecessary.
Anyway, let me quickly show how I've debugged this issue to find where the error comes from in a couple of minutes. I'll first show you the code that I added to the passthrough sample to detect when this case happens:
    if (PtDoRequestOperationStatus( Data )) {

status = FltRequestOperationStatusCallback( Data,
PtOperationStatusCallback,
(PVOID)(++OperationStatusCtx) );
if (!NT_SUCCESS(status)) {

PT_DBG_PRINT( PTDBG_TRACE_OPERATION_STATUS,
("PassThrough!PtPreOperationPassThrough: FltRequestOperationStatusCallback Failed, status=%08x\n",
status) );
}
}

if (Data->Iopb->MajorFunction == IRP_MJ_CREATE) {

status = FltGetFileNameInformation( Data,
FLT_FILE_NAME_NORMALIZED,
&fileName );

if (NT_SUCCESS(status)) {

DbgPrint("preCreate|normalized -> \"%wZ\"\n", &fileName->Name);

FltReleaseFileNameInformation( fileName );

} else {

DbgBreakPoint();

status = FltGetFileNameInformation( Data,
FLT_FILE_NAME_NORMALIZED,
&fileName );

}

As you can see, when the call to FltGetFileNameInformation fails I've added a breakpoint and then I retry the operation with the exact same parameters, which allows me to investigate the call. After that, when the breakpoint triggers, I do this:
Break instruction exception - code 80000003 (first chance)    <- here I've hit the breakpoint
PassThrough!PtPreOperationPassThrough+0xd2:
a414c0f2 cc              int     3
0: kd> p <- step over the breakpoint
PassThrough!PtPreOperationPassThrough+0xd3:
a414c0f3 8d45f8          lea     eax,[ebp-8]
0: kd> t <- trace into the function
fltmgr!FltGetFileNameInformation:
9601ce78 8bff            mov     edi,edi
0: kd> pc <- find the next call
fltmgr!FltGetFileNameInformation+0x118:
9601cf90 e833010000      call    fltmgr!FltpAllocateInitializeNameGenerationContext (9601d0c8)
0: kd> p <- and step over it
fltmgr!FltGetFileNameInformation+0x11d:
9601cf95 8bf0            mov     esi,eax
0: kd> r <- and now inspect the registers. In this calling convention eax will be the NTSTATUS , so eax = 00000000 means STATUS_SUCCESS
eax=00000000 ebx=92639008 ecx=944f6ae0 edx=944f6ae0 esi=92639068 edi=00000000
eip=9601cf95 esp=a194d96c ebp=a194d988 iopl=0         nv up ei pl zr na pe nc
cs=0008  ss=0010  ds=0023  es=0023  fs=0030  gs=0000             efl=00000246
fltmgr!FltGetFileNameInformation+0x11d:
9601cf95 8bf0            mov     esi,eax
0: kd> pc <- ok, find the next call
fltmgr!FltGetFileNameInformation+0x126:
9601cf9e e85df8ffff      call    fltmgr!FltpGetFileNameInformation (9601c800)
0: kd> p <- step over it
fltmgr!FltGetFileNameInformation+0x12b:
9601cfa3 8bf0            mov     esi,eax
0: kd> r <- inspect the result again and note that eax=c00000d4, which happens to be STATUS_NOT_SAME_DEVICE .
eax=c00000d4 ebx=92639008 ecx=00000000 edx=00000003 esi=00000000 edi=00000000
eip=9601cfa3 esp=a194d96c ebp=a194d988 iopl=0         nv up ei pl zr na pe nc
cs=0008  ss=0010  ds=0023  es=0023  fs=0030  gs=0000             efl=00000246
fltmgr!FltGetFileNameInformation+0x12b:
9601cfa3 8bf0            mov     esi,eax

So now I know that the STATUS_NOT_SAME_DEVICE error came from the call to fltmgr!FltpGetFileNameInformation. Time to continue this investigation, but this time looking into that function:
0: kd> g <- hit go and trigger the condition (which in my case was trying to traverse a mountpoint so I just did a notepad C:\mnt\foo.txt, where C:\mnt was a mount point)
Break instruction exception - code 80000003 (first chance)
PassThrough!PtPreOperationPassThrough+0xd2:
a414c0f2 cc              int     3 <- so I hit the breakpoint again, as expected.
0: kd> bp /t @$thread fltmgr!FltpGetFileNameInformation <- set a threaded breakpoint on the function where I know the failure should happen. The thread is useful when a function is called from multiple threads and I don't want the breakpoint to trigger for those. 0: kd> g <- hit go and we should hit the breakpoint when the current thread enters that function Breakpoint 0 hit <- and so it is... fltmgr!FltpGetFileNameInformation: 9601c800 8bff mov edi,edi 0: kd> bc * <- clear the breakpoint . This is sometimes necessary because if there is recursion it will hit again on the same thread and might confuse things 0: kd> pc <- find the first call fltmgr!FltpGetFileNameInformation+0x48: 9601c848 e8db9bffff call fltmgr!FltpGetNextCallbackNodeForInstance (96016428) 0: kd> p <- and step over to see the status fltmgr!FltpGetFileNameInformation+0x4d: 9601c84d 894614 mov dword ptr [esi+14h],eax 0: kd> r <- check the status, which is STATUS_SUCCESS eax=00000000 ebx=92639008 ecx=9444cd48 edx=00000000 esi=94501858 edi=00000000 eip=9601c84d esp=a194d864 ebp=a194d888 iopl=0 nv up ei pl zr na pe nc cs=0008 ss=0010 ds=0023 es=0023 fs=0030 gs=0000 efl=00000246 fltmgr!FltpGetFileNameInformation+0x4d: 9601c84d 894614 mov dword ptr [esi+14h],eax ds:0023:9450186c=00000000 0: kd> pc <- find the next call fltmgr!FltpGetFileNameInformation+0x5a: 9601c85a e8c99bffff call fltmgr!FltpGetNextCallbackNodeForInstance (96016428) 0: kd> p <- step again fltmgr!FltpGetFileNameInformation+0x5f: 9601c85f 894618 mov dword ptr [esi+18h],eax 0: kd> r <- STATUS_SUCCESS again eax=00000000 ebx=92639008 ecx=9444cd48 edx=00000000 esi=94501858 edi=00000000 eip=9601c85f esp=a194d864 ebp=a194d888 iopl=0 nv up ei pl zr na pe nc cs=0008 ss=0010 ds=0023 es=0023 fs=0030 gs=0000 efl=00000246 fltmgr!FltpGetFileNameInformation+0x5f: 9601c85f 894618 mov dword ptr [esi+18h],eax ds:0023:94501870=00000000 0: kd> pc <- and then the next call fltmgr!FltpGetFileNameInformation+0xb2: 9601c8b2 e829160000 call fltmgr!FltpGetStreamListCtrl (9601dee0) 0: kd> p fltmgr!FltpGetFileNameInformation+0xb7: 9601c8b7 894508 mov dword ptr [ebp+8],eax 0: kd> r <- this fails with STATUS_NOT_SUPPORTED. This might be a failure that gets converted into the one we're looking for. I investigated it (not shown here) but it doesn't result in a failure, it just changes the code path through the function eax=c00000bb ebx=92639008 ecx=9601e0a8 edx=00000000 esi=94501858 edi=00000000 eip=9601c8b7 esp=a194d864 ebp=a194d888 iopl=0 nv up ei pl zr na pe nc cs=0008 ss=0010 ds=0023 es=0023 fs=0030 gs=0000 efl=00000246 fltmgr!FltpGetFileNameInformation+0xb7: 9601c8b7 894508 mov dword ptr [ebp+8],eax ss:0010:a194d890=94501858 0: kd> pc <-find the next call fltmgr!FltpGetFileNameInformation+0xc2: 9601c8c2 e887fdffff call fltmgr!HandleStreamListNotSupported (9601c64e) 0: kd> p <- step over fltmgr!FltpGetFileNameInformation+0xc7: 9601c8c7 894508 mov dword ptr [ebp+8],eax 0: kd> r <- and we can see that we've hit the status we wanted, eax=c00000d4. so now we know the failure comes from fltmgr!HandleStreamListNotSupported, so set a breakpoint on it. eax=c00000d4 ebx=92639008 ecx=00000000 edx=00000003 esi=94501858 edi=00000000 eip=9601c8c7 esp=a194d864 ebp=a194d888 iopl=0 nv up ei pl nz na po nc cs=0008 ss=0010 ds=0023 es=0023 fs=0030 gs=0000 efl=00000202 fltmgr!FltpGetFileNameInformation+0xc7: 9601c8c7 894508 mov dword ptr [ebp+8],eax ss:0010:a194d890=c00000bb 0: kd> g <- so now we need to go back to trigger the breakpoint Break instruction exception - code 80000003 (first chance) PassThrough!PtPreOperationPassThrough+0xd2: a414c0f2 cc int 3 0: kd> bp /t@$thread fltmgr!HandleStreamListNotSupported  <- set our threaded breakpoint on that function
0: kd> g <- and run
Breakpoint 0 hit
fltmgr!HandleStreamListNotSupported:
9601c64e 8bff            mov     edi,edi

After a couple of iterations (in about 5 minutes of debugging) we end up with this stack, where the status is actually generated.:
0: kd> k
a194d8ac 96034c59 fltmgr!FltpExpandFilePathWorker+0x2b3
a194d8c4 96034dc3 fltmgr!FltpExpandFilePath+0x19
a194d8e0 96035505 fltmgr!FltpGetNormalizedFileNameWorker+0x7d
a194d8f8 96032765 fltmgr!FltpGetNormalizedFileName+0x19
a194d910 9601c773 fltmgr!FltpCreateFileNameInformation+0x81
a194d930 9601c8c7 fltmgr!HandleStreamListNotSupported+0x125
a194d960 9601cfa3 fltmgr!FltpGetFileNameInformation+0xc7
a194d988 a414c102 fltmgr!FltGetFileNameInformation+0x12b
a194d9ac 96016aeb PassThrough!PtPreOperationPassThrough+0xe2 [c:\temp11\passthrough\passthrough.c @ 705]
a194da18 960199f0 fltmgr!FltpPerformPreCallbacks+0x34d
a194da30 9602d1fe fltmgr!FltpPassThroughInternal+0x40
a194da44 9602d8b7 fltmgr!FltpCreateInternal+0x24
a194da88 828884bc fltmgr!FltpCreate+0x2c9


text:
# Second-Order Integrator

Second-order integration of input signal

• Library:

## Description

The Second-Order Integrator block and the Second-Order Integrator Limited block solve the second-order initial value problem:

`$\begin{array}{l}\frac{{d}^{2}x}{d{t}^{2}}=u,\\ {\frac{dx}{dt}|}_{t=0}=d{x}_{o},\\ {x|}_{t=0}={x}_{o},\end{array}$`

where u is the input to the system. The block is therefore a dynamic system with two continuous states: x and dx/dt.

Note

These two states have a mathematical relationship, namely, that dx/dt is the derivative of x. To satisfy this relationship throughout the simulation, Simulink places various constraints on the block parameters and behavior.

The Second-Order Integrator Limited block is identical to the Second-Order Integrator block with the exception that it defaults to limiting the states based on the specified upper and lower limits. For more information, see Limiting the States.

Simulink® software can use several different numerical integration methods to compute the outputs of the block. Each has advantages for specific applications. Use the Solver pane of the Configuration Parameters dialog box to select the technique best suited to your application. (For more information, see Solver Selection Criteria.) The selected solver computes the states of the Second-Order Integrator block at the current time step using the current input value.

Use the block parameter dialog box to:

• Specify whether the source of each state initial condition is internal or external

• Specify a value for the state initial conditions

• Define upper and lower limits on either or both states

• Specify absolute tolerances for each state

• Specify names for both states

• Choose an external reset condition

• Enable zero-crossing detection

• Reinitialize dx/dt when x reaches saturation

• Specify that Simulink disregard the state limits and external reset for linearization operations

### Defining Initial Conditions

You can define the initial conditions of each state individually as a parameter on the block dialog box or input one or both of them from an external signal.

• To define the initial conditions of state x as a block parameter, use the Initial condition source x drop-down menu to select `internal` and enter the value in the Initial condition x field.

• To provide the initial conditions from an external source for state x, specify the Initial condition source x parameter as `external`. An additional input port appears on the block.

• To define the initial conditions of state dx/dt as a block parameter, use the Initial condition source dx/dt drop-down menu to select `internal` and enter the value in the Initial condition dx/dt field.

• To provide the initial conditions from an external source for state dx/dt, specify Initial condition source dx/dt as `external`. An additional input port appears on the block.

If you choose to use an external source for both state initial conditions, your block appears as follows.

Note

• Simulink does not allow initial condition values of `inf` or `NaN`.

• If you limit state x or state dx/dt by specifying saturation limits (see Limiting the States) and one or more initial conditions are outside the corresponding limits, then the respective states are initialized to the closest valid value and a set of consistent initial conditions is calculated.

### Limiting the States

When modeling a second-order system, you may need to limit the block states. For example, the motion of a piston within a cylinder is governed by Newton's Second Law and has constraints on the piston position (x). With the Second-Order Integrator block, you can limit the states x and dx/dt independent of each other. You can even change the limits during simulation; however, you cannot change whether or not the states are limited. An important rule to follow is that an upper limit must be strictly greater than its corresponding lower limit.

The block appearance changes when you limit one or both states. With both states limited, the block appears as follows.

For each state, you can use the block parameter dialog box to set appropriate saturation limits.

### Limiting x Only

If you use the Second-Order Integrator Limited block, both states are limited by default. But you can also manually limit state x on the Second-Order Integrator block by selecting Limit x and entering the limits in the appropriate parameter fields.

The block then determines the values of the states as follows:

• When x is less than or equal to its lower limit, the value of x is held at its lower limit and dx/dt is set to zero.

• When x is in between its lower and upper limits, both states follow the trajectory given by the second-order ODE.

• When x is greater than or equal to its upper limit, the value of x is held at its upper limit and dx/dt is set to zero.

You can choose to reinitialize dx/dt to a new value at the time when x reaches saturation. See Reinitializing dx/dt When x Reaches Saturation.

### Limiting dx/dt Only

As with state x, state dx/dt is set as limited by default on the dx/dt pane of the Second-Order Integrator Limited block dialog box. You can manually set this parameter, Limit dx/dt, on the Second-Order Integrator block. In either case, you must enter the appropriate limits for dx/dt.

If you limit only the state dx/dt, then the block determines the values of dx/dt as follows:

• When dx/dt is less than or equal to its lower limit, the value of dx/dt is held at its lower limit.

• When dx/dt is in between its lower and upper limits, both states follow the trajectory given by the second-order ODE.

• When dx/dt is greater than or equal to its upper limit, the value of dx/dt is held at its upper limit.

When state dx/dt is held at it upper or lower limit, the value of x is governed by the first-order initial value problem:

`$\begin{array}{l}\frac{dx}{dt}=L,\\ x\left({t}_{L}\right)={x}_{L,}\end{array}$`

where L is the dx/dt limit (upper or lower), tL is the time when dx/dt reaches this limit, and xL is the value of state x at that time.

### Limiting Both States

When you limit both states, Simulink maintains mathematical consistency of the states by limiting the allowable values of the upper and lower limits for dx/dt. Such limitations are necessary to satisfy the following constraints:

• When x is at its saturation limits, the value of dx/dt must be zero.

• In order for x to leave the upper limit, the value of dx/dt must be strictly negative.

• In order for x to leave its lower limit, the value of dx/dt must be strictly positive.

For such cases, the upper limit of dx/dt must be strictly positive and the lower limit of dx/dt must be strictly negative.

When both states are limited, the block determines the states as follows:

• Whenever x reaches its limits, the resulting behavior is the same as that described in “Limiting x only”.

• Whenever dx/dt reaches one of its limits, the resulting behavior is the same as that described in “Limiting dx/dt only” — including the computation of x using a first-order ODE when dx/dt is held at one of its limits. In such cases, when x reaches one of its limits, it is held at that limit and dx/dt is set to zero.

• Whenever both reach their respective limits simultaneously, the state x behavior overrides dx/dt behavior to maintain consistency of the states.

When you limit both states, you can choose to reinitialize dx/dt at the time when state x reaches saturation. If the reinitialized value is outside specified limits on dx/dt, then dx/dt is reinitialized to the closest valid value and a consistent set of initial conditions is calculated. See Reinitializing dx/dt When x Reaches Saturation

### Resetting the State

The block can reset its states to the specified initial conditions based on an external signal. To cause the block to reset its states, select one of the External reset choices on the Attributes pane. A trigger port appears on the block below its input port and indicates the trigger type.

• Select `rising` to reset the states when the reset signal rises from zero to a positive value, from a negative to a positive value, or a negative value to zero.

• Select `falling` to reset the states when the reset signal falls from a positive value to zero, from a positive to a negative value, or from zero to negative.

• Select `either` to reset the states when the reset signal changes from zero to a nonzero value or changes sign.

The reset port has direct feedthrough. If the block output feeds back into this port, either directly or through a series of blocks with direct feedthrough, an algebraic loop results (see Algebraic Loop Concepts).

### Enabling Zero-Crossing Detection

This parameter controls whether zero-crossing detection is enabled for this block. By default, the Enable zero-crossing detection parameter is selected on the Attributes pane. However, this parameter is only in affect if the Zero-crossing control, on the Solver pane of the Configuration Parameters dialog box, is set to `Use local settings`. For more information, see Zero-Crossing Detection.

### Reinitializing dx/dt When x Reaches Saturation

For certain modeling applications, dx/dt must be reinitialized when state x reaches its limits in order to pull x out of saturation immediately. You can achieve this by selecting Reinitialize dx/dt when x reaches saturation on the Attributes pane.

If this option is on, then at the instant when x reaches saturation, Simulink checks whether the current value of the dx/dt initial condition (parameter or signal) allows the state x to leave saturation immediately. If so, Simulink reinitializes state dx/dt with the value of the initial condition (parameter or signal) at that instant. If not, Simulink ignores this parameter at the current instant and sets dx/dt to zero to make the block states consistent.

This parameter only applies at the time when x actually reaches saturation limit. It does not apply at any future time when x is being held at saturation.

Refer to the sections on limiting the states for more information. For an example, see Simulation of Bouncing Ball.

### Disregarding State Limits and External Reset for Linearization

For cases where you simplify your model by linearizing it, you can have Simulink disregard the limits of the states and the external reset by selecting Ignore state limits and the reset for linearization.

### Specifying the Absolute Tolerance for the Block Outputs

By default Simulink software uses the absolute tolerance value specified in the Configuration Parameters dialog box (see Error Tolerances for Variable-Step Solvers) to compute the output of the integrator blocks. If this value does not provide sufficient error control, specify a more appropriate value for state x in the Absolute tolerance x field and for state dx/dt in the Absolute tolerance dx/dt field of the parameter dialog box. Simulink uses the values that you specify to compute the state values of the block.

### Specifying the Display of the Output Ports

You can control whether to display the x or the dx/dt output port using the `ShowOutput` parameter. You can display one output port or both; however, you must select at least one.

### Specifying the State Names

You can specify the name of x states and dx/dt states using the `StateNameX` and `StateNameDXDT` parameters. However, you must specify names for both or neither; you cannot specify names for just x or just dx/dt. Both state names must have identical type and length. Furthermore, the number of names must evenly divide the number of states.

### Selecting All Options

When you select all options, the block icon looks like this.

## Ports

### Input

expand all

Input signal `u` to the integrator system, specified as a scalar, vector, or matrix.

Data Types: `double`

External signal specifying the initial condition `x0` to the integrator system. You can specify the initial condition as a scalar, vector, or matrix.

#### Dependencies

To enable this input port, set the Initial condition source x parameter to `external`.

Data Types: `double`

External signal specifying the initial condition `dx0` to the integrator system. You can specify the initial condition `dx0` as a scalar, vector, or matrix.

#### Dependencies

To enable this input port, set the Initial condition source dx/dt parameter to `external`.

Data Types: `double`

### Output

expand all

`x` state output signal, provided as a scalar, vector, or matrix.

Data Types: `double`

`dx` state output signal, specified as a scalar, vector, or matrix.

Data Types: `double`

## Parameters

expand all

### x

Specify the source of the initial conditions for state x.

• `internal` — Get the initial conditions of state x from the Initial condition x parameter.

• `external` — Get the initial conditions of state x from an external block connected to the X0 input port.

#### Limitations

Simulink software does not allow the initial condition of this block to be `inf` or `NaN`.

#### Dependencies

Selecting `internal` enables the Initial condition x parameter and removes the X0 input port.

Selecting `external` disables the Initial condition x parameter and enables the X0 input port.

#### Programmatic Use

 Block Parameter: `ICSourceX` Type: character vector, string Values: `'internal'` | `'external'` Default: `'internal'`

Specify the initial condition of state x.

#### Limitations

Simulink software does not allow the initial condition of this block to be `inf` or `NaN`.

#### Dependencies

To enable this parameter, set Initial condition source x to `internal`.

Setting Initial condition source x to `external` disables this parameter and enables the X0 input port.

#### Programmatic Use

 Block Parameter: `ICX` Type: character vector, string Values: scalar | vector | matrix Default: `'0.0'`

Limit state x of the block to a value between the Lower limit x and Upper limit x parameters. The default value of the Second-Order Integrator block is `off`. The default value of the Second-Order Integrator Limited is `on`.

• To limit state x to a value between the Lower limit x and Upper limit x parameters, select this check box.

• To remove range limitations on state x, clear this check box.

#### Dependencies

Selecting this check box enables the Upper limit x and Lower limit x parameters.

#### Programmatic Use

 Block Parameter: `LimitX` Type: character vector, string Values: `'off'` | `'on'` Default: `'off'` (Second-Order Integrator) | `'on'` (Second-Order Integrator Limited)

Specify the upper limit of state x. The default value for the Second-Order Integrator block is `inf`. The default value for the Second-Order Integrator Limited block is `1`.

#### Tips

The upper saturation limit for state x must be strictly greater than the lower saturation limit.

#### Dependencies

To enable this parameter, select the Limit x check box.

#### Programmatic Use

 Block Parameter: `UpperLimitX` Type: character vector, string Values: `'1' | 'inf' |` scalar | vector | matrix Default: `'1'` (Second-Order Integrator Limited) | `'inf'` (Second-Order Integrator)

Specify the lower limit of state x. The default value for the Second-Order Integrator block is `-inf`. The default value for the Second-Order Integrator Limited block is `0`.

#### Tip

The lower saturation limit for state x must be strictly less than the upper saturation limit.

#### Dependencies

To enable this parameter, select the Limit x check box.

#### Programmatic Use

 Block Parameter: `LowerLimitX` Type: character vector, string Values: `'0' | '-inf' |` scalar | vector | matrix Default: `'0'` (Second-Order Integrator Limited) | `'-inf'` (Second-Order Integrator)

Enable wrapping of x between the Wrapped upper value x and Wrapped lower value x parameters. Enabling wrapping of x eliminates the need for zero-crossing detection, reduces solver resets, improves solver performance and accuracy, and increases simulation time span when modeling rotary and cyclic state trajectories.

If you specify Wrapped upper value x as `inf` and Wrapped lower value x as `-inf`, wrapping will never occur.

#### Dependencies

Selecting this check box enables Wrapped upper value x and Wrapped lower value x.

#### Programmatic Use

 Block Parameter: `WrapX` Type: character vector, string Values: `'off'` | `'on'` Default: `'off'`

Specify the upper value for wrapping x.

#### Dependencies

To enable this parameter, select the Wrap x check box.

#### Programmatic Use

 Block Parameter: `WrappedUpperValueX` Type: character vector, string Values: scalar | vector | matrix Default: `'pi'`

Specify the lower value for wrapping x.

#### Dependencies

To enable this parameter, select the Wrap x check box.

#### Programmatic Use

 Block Parameter: `WrappedLowerValueX` Type: character vector, string Values: scalar | vector | matrix Default: `'-pi'`

Specify the absolute tolerance for computing state x.

• You can enter `auto`, –1, a positive real scalar or vector.

• If you enter `auto` or –1, Simulink uses the absolute tolerance value in the Configuration Parameters dialog box (see Solver Pane) to compute state x.

• If you enter a real scalar value, that value overrides the absolute tolerance in the Configuration Parameters dialog box and is used for computing all x states.

• If you enter a real vector, the dimension of that vector must match the dimension of state x. These values override the absolute tolerance in the Configuration Parameters dialog box.

#### Programmatic Use

 Block Parameter: ` AbsoluteToleranceX` Type: character vector, string Values: `'auto'` | `'-1'` | any positive real scalar or vector Default: `'auto'`

Assign a unique name to state x.

#### Tips

• To assign a name to a single state, enter the name between quotes, for example, position'.

• To assign names to multiple x states, enter a comma-delimited list surrounded by braces, for example, {'a', 'b', 'c'}. Each name must be unique.

• The state names apply only to the selected block.

• If you specify a state name for x, you must also specify a state name for dx/dt.

• State names for x and dx/dt must have identical types and lengths.

• The number of states must be evenly divided by the number of state names. You can specify fewer names than x states, but you cannot specify more names than x states. For example, you can specify two names in a system with four states. The first name applies to the first two states and the second name to the last two states. However, you must be consistent and apply the same scheme to the state names for dx/dt.

• To assign state names with a variable in the MATLAB® workspace, enter the variable without quotes. A variable can be a character vector, string or a cell array.

#### Programmatic Use

 Block Parameter: `StateNameX` Type: character vector, string Values: `' '` | user-defined Default: `' '`

### dx/dt

Specify the source of initial conditions for state dx/dt as `internal` or `external`.

#### Limitations

Simulink software does not allow the initial condition of this block to be `inf` or `NaN`.

#### Dependencies

• Selecting `internal` enables the Initial condition dx/dt parameter and removes the dx0 input port.

• Selecting `external` disables the Initial condition dx/dt parameter and enables the dx0 input port.

#### Programmatic Use

 Block Parameter: `ICSourceDXDT` Type: character vector Values: `'internal'` | `'external'` Default: `'internal'`

Specify the initial condition of state dx/dt.

#### Limitations

Simulink software does not allow the initial condition of this block to be `inf` or `NaN`.

#### Dependencies

• Setting Initial condition source dx/dt to `internal` enables this parameter.

• Setting Initial condition source dx/dt to `external` disables this parameter.

#### Programmatic Use

 Block Parameter: `ICDXDT` Type: character vector Values: scalar | vector | matrix Default: `'0.0'`

Limit the dx/dt state of the block to a value between the Lower limit dx/dt and Upper limit dx/dt parameters. The default value of the Second-Order Integrator block is `off`. The default value of the Second-Order Integrator Limited is `on`.

#### Tip

If you set saturation limits for x, then the interval defined by the Upper limit dx/dt and Lower limit dx/dt must contain zero.

#### Dependencies

Selecting this check box enables the Upper limit dx/dt and Lower limit dx/dt parameters.

#### Programmatic Use

 Parameter: `LimitDXDT` Type: character vector Values: `'off'` | `'on'` Default: `'off'` (Second-Order Integrator) | `'on'` (Second-Order Integrator Limited)

Specify the upper limit for state dx/dt.

#### Dependencies

If you limit x, then this parameter must have a strictly positive value.

To enable this parameter, select the Limit dx/dt check box.

#### Programmatic Use

 Block Parameter: `UpperLimitDXDT` Type: character vector Values: scalar | vector | matrix Default: `'inf'`

Specify the lower limit for state dx/dt.

#### Dependencies

If you limit x, then this parameter must have a strictly negative value.

To enable this parameter, select the Limit dx/dt check box.

#### Programmatic Use

 Block Parameter: `LowerLimitDXDT` Type: character vector Values: scalar | vector | matrix Default: `'-inf'`

Specify the absolute tolerance for computing state dx/dt.

• You can enter `auto`, `–1`, a positive real scalar or vector.

• If you enter `auto` or `–1`, then Simulink uses the absolute tolerance value in the Configuration Parameters dialog box (see Solver Pane) to compute the dx/dt output of the block.

• If you enter a numeric value, that value overrides the absolute tolerance in the Configuration Parameters dialog box.

#### Programmatic Use

 Block Parameter: ` AbsoluteToleranceDXDT` Type: character vector, string, scalar, or vector Values: `'auto'` | `'-1'` | any positive real scalar or vector Default: `'auto'`

Assign a unique name to state dx/dt.

#### Tips

• To assign a name to a single state, enter the name between quotes, for example, 'velocity'.

• To assign names to multiple dx/dt states, enter a comma-delimited list surrounded by braces, for example, {'a', 'b', 'c'}. Each name must be unique.

• The state names apply only to the selected block.

• If you specify a state name for dx/dt, you must also specify a state name for x.

• State names for x and dx/dt must have identical types and lengths.

• The number of states must be evenly divided by the number of state names. You can specify fewer names than dx/dt states, but you cannot specify more names than dx/dt states. For example, you can specify two names in a system with four states. The first name applies to the first two states and the second name to the last two states. However, you must be consistent and apply the same scheme to the state names for x.

• To assign state names with a variable in the MATLAB workspace, enter the variable without quotes. A variable can be a character vector, string, or a cell array.

#### Programmatic Use

 Block Parameter: `StateNameDXDT` Type: character vector, string Values: `' '` | user-defined Default: `' '`

### Attributes

Reset the states to their initial conditions when a trigger event occurs in the reset signal.

• `none` — Do not reset the state to initial conditions.

• `rising` — Reset the state when the reset signal rises from a zero to a positive value or from a negative to a positive value.

• `falling` — Reset the state when the reset signal falls from a positive value to zero or from a positive to a negative value.

• `either` — Reset the state when the reset signal changes from zero to a nonzero value or changes sign.

#### Programmatic Use

 Block Parameter: `ExternalReset` Type: character vector, string Values: `'none'` | `'rising'` | `'falling'` | `'either'` Default: `'none'`

#### Programmatic Use

 Parameter: `ZeroCross` Type: character vector, string Values: `'on'` | `'off'` Default: `'on'`

At the instant when state x reaches saturation, reset dx/dt to its current initial conditions.

#### Tip

The dx/dt initial condition must have a value that enables x to leave saturation immediately. Otherwise, Simulink ignores the initial conditions for dx/dt to preserve mathematical consistency of block states.

#### Programmatic Use

 Block Parameter: ` ReinitDXDTwhenXreachesSaturation` Type: character vector, string Values: `'off'` | `'on'` Default: `'off'`

For linearization purposes, have Simulink ignore the specified state limits and the external reset.

#### Programmatic Use

 Block Parameter: ` IgnoreStateLimitsAndResetForLinearization` Type: character vector, string Values: `'off'` | `'on'` Default: `'off'`

Specify the output ports on the block.

• `both` — Show both x and dx/dt output ports.

• `x` — Show only the x output port.

• `dx/dt` — Show only the dx/dt output port.

#### Programmatic Use

 Block Parameter: `ShowOutput` Type: character vector, string Values: `'both'` | `'x'` | `'dxdt'` Default: `'both'`

## Block Characteristics

 Data Types `double` Direct Feedthrough `yes` Multidimensional Signals `no` Variable-Size Signals `no` Zero-Crossing Detection `yes`

## Version History

Introduced in R2010a

format: plain


text:
Lemma 79.5.4. Let $S$ be a scheme. Let $F : (\mathit{Sch}/S)_{fppf}^{opp} \to \textit{Sets}$ be a functor. Let $X$ be a scheme and let $X \to F$ be representable by algebraic spaces and locally quasi-finite. Then $X \to F$ is representable (by schemes).

Proof. Let $T$ be a scheme and let $T \to F$ be a morphism. We have to show that the algebraic space $X \times _ F T$ is representable by a scheme. Consider the morphism

$X \times _ F T \longrightarrow X \times _{\mathop{\mathrm{Spec}}(\mathbf{Z})} T$

Since $X \times _ F T \to T$ is locally quasi-finite, so is the displayed arrow (Morphisms of Spaces, Lemma 66.27.8). On the other hand, the displayed arrow is a monomorphism and hence separated (Morphisms of Spaces, Lemma 66.10.3). Thus $X \times _ F T$ is a scheme by Morphisms of Spaces, Proposition 66.50.2. $\square$

In your comment you can use Markdown and LaTeX style mathematics (enclose it like $\pi$). A preview option is available if you wish to see how it works out (just click on the eye in the toolbar).


text:
# Dimensionality reduction (SVD or PCA) on a large, sparse matrix

I have a large, sparse Matrix of features I would like to use in a machine learning algorithm:

library(Matrix)
set.seed(42)
rows <- 500000
cols <- 10000
i <- unlist(lapply(1:rows, function(i) rep(i, sample(1:5,1))))
j <- sample(1:cols, length(i), replace=TRUE)
M <- sparseMatrix(i, j)

Because this matrix has many columns, I would like to reduce its dimensionality to something more manageable. I can use the excellent irlba package to perform SVD and return the first n principal components (5 shown here; I'll probably use 100 or 500 on my actual dataset):

library(irlba)
pc <- irlba(M, nu=5)$u  However, I've read that prior to performing PCA, one should center the matrix (subtract the column mean from each column). This is very difficult to do on my dataset, and furthermore would destroy the sparsity of the matrix. How "bad" is it to perform SVD on the un-scaled data, and feed it straight into a machine learning algorithm? Are there any efficient ways I could scale this data, while preserving the sparsity of the matrix? /edit: A brought to my attention by B_miner, the "PCs" should really be: pc <- M %*% irlba(M, nv=5, nu=0)$v

Also, I think whuber's answer should be pretty easy to implement, via the crossprod function, which is extremely fast on sparse matrices:

system.time(M_Mt <- crossprod(M)) # 0.463 seconds
system.time(means <- colMeans(M)) #0.003 seconds

Now I'm not quite sure what to do to the means vector before subtracting from M_Mt, but will post as soon as I figure it out.

/edit3: Here's modified version of whuber's code, using sparse matrix operations for each step of the process. If you can store the entire sparse matrix in memory, it works very quickly:

library('Matrix')
library('irlba')
set.seed(42)
m <- 500000
n <- 100
i <- unlist(lapply(1:m, function(i) rep(i, sample(25:50,1))))
j <- sample(1:n, length(i), replace=TRUE)
x <- sparseMatrix(i, j, x=runif(length(i)))

n_comp <- 50
system.time({
xt.x <- crossprod(x)
x.means <- colMeans(x)
xt.x <- (xt.x - m * tcrossprod(x.means)) / (m-1)
svd.0 <- irlba(xt.x, nu=0, nv=n_comp, tol=1e-10)
})
#user  system elapsed
#0.148   0.030   2.923

system.time(pca <- prcomp(x, center=TRUE))
#user  system elapsed
#32.178   2.702  12.322

max(abs(pca$center - x.means)) max(abs(xt.x - cov(as.matrix(x)))) max(abs(abs(svd.0$v / pca$rotation[,1:n_comp]) - 1))  If you set the number of columns to 10,000 and the number of principal components to 25, the irlba-based PCA takes about 17 minutes to calculate 50 approximate principal components and consumes about 6GB of RAM, which isn't too bad. - Zach, curious if you ever solved this. – B_Miner Jul 17 at 17:45 @B_Miner: Basically, I've been doing SVD without bothering to center or scale first, because I've never found a good way to do this without converting my sparse matrix to a dense matrix. The original matrix %*% the svd's V component gives the "principle components." Sometimes, I get better results if I "fold in" the eigen values, e.g v %*% diag(d), where d is the vector of eigenvalues from the SVD. – Zach Jul 17 at 17:49 Do you treat v %*% diag(d) by itself or still multiplied by the original matrix X (i.e. X%*% v %*% diag(d)). It seems above you are using the u matrix as the principal component scores? – B_Miner Jul 17 at 18:32 I use X %*% v %*% diag(d, ncol=length(d)). The v matrix in the svd is equivalent to the "rotation" element of a prcomp object, and X %*% v or X %*% v %*% diag(d, ncol=length(d)) represents the x element of a prcomp object. Take a look a stats:::prcomp.default. – Zach Jul 17 at 18:41 Yes, X %*% v is the x element from prcomp. It looks like when you use the u matrix as in your question, you are actually using X %*% v %*% diag(1/d). – B_Miner Jul 17 at 18:49 show 2 more comments ## 1 Answer First of all, you really do want to center the data. If not, the geometric interpretation of PCA shows that the first principal component will be close to the vector of means and all subsequent PCs will be orthogonal to it, which will prevent them from approximating any PCs that happen to be close to that first vector. We can hope that most of the later PCs will be approximately correct, but the value of that is questionable when it's likely the first several PCs--the most important ones--will be quite wrong. So, what to do? PCA proceeds by means of a singular value decomposition of the matrix$X$. The essential information will be contained in$X X'$, which in this case is a$10000$by$10000$matrix: that may be manageable. Its computation involves about 50 million calculations of dot products of one column with the next. Consider any two columns, then,$Y$and$Z$(each one of them is a$500000$-vector; let this dimension be$n$). Let their means be$m_Y$and$m_Z$, respectively. What you want to compute is, writing$\mathbf{1}$for the$n$-vector of$1$'s, $$(Y - m_Y\mathbf{1}) \cdot (Z - m_Z\mathbf{1}) = Y\cdot Z - m_Z\mathbf{1}\cdot Y - m_Y\mathbf{1}.Z + m_Z m_Y \mathbf{1}\cdot \mathbf{1}\\ = Y\cdot Z -n (m_Ym_Z),$$ because$m_Y = \mathbf{1}\cdot Y / n$and$m_Z = \mathbf{1}\cdot Z/n$. This allows you to use sparse matrix techniques to compute$X X'$, whose entries provide the values of$Y\cdot Z$, and then adjust its coefficients based on the$10000$column means. The adjustment shouldn't hurt, because it seems unlikely$X X'$will be very sparse. ### Example The following R code demonstrates this approach. It uses a stub, get.col, which in practice might read one column of$X$at a time from an external data source, thereby reducing the amount of RAM required (at some cost in computation speed, of course). It computes PCA in two ways: via SVD applied to the preceding construction and directly using prcomp. It then compares the output of the two approaches. The computation time is about 50 seconds for 100 columns and scales approximately quadratically: be prepared to wait when performing SVD on a 10K by 10K matrix! m <- 500000 # Will be 500,000 n <- 100 # will be 10,000 library("Matrix") x <- as(matrix(pmax(0,rnorm(m*n, mean=-2)), nrow=m), "sparseMatrix") # # Compute centered version of x'x by having at most two columns # of x in memory at any time. # get.col <- function(i) x[,i] # Emulates reading a column system.time({ xt.x <- matrix(numeric(), n, n) x.means <- rep(numeric(), n) for (i in 1:n) { i.col <- get.col(i) x.means[i] <- mean(i.col) xt.x[i,i] <- sum(i.col * i.col) if (i < n) { for (j in (i+1):n) { j.col <- get.col(j) xt.x[i,j] <- xt.x[j,i] <- sum(j.col * i.col) } } } xt.x <- (xt.x - m * outer(x.means, x.means, *)) / (m-1) svd.0 <- svd(xt.x / m) } ) system.time(pca <- prcomp(x, center=TRUE)) # # Checks: all should be essentially zero. # max(abs(pca$center - x.means))
max(abs(xt.x - cov(x)))
max(abs(abs(svd.0$v / pca$rotation) - 1)) # (This is an unstable calculation.)

-
Thank you for the detailed answer. One of the advantages of irlba is that you can specify nu to limit the algorithm to the first n principle components, which greatly increases it's efficacy and (I think) bypasses the calculation of the XX' matrix. –  Zach Aug 27 '12 at 20:50
But what do you want to work with? A sparse $10000$ by $500000$ matrix with $5\times 10^9$ coefficients that does not represent the problem you need to solve, or a $10000$ by $10000$ with $10^8$ coefficients that does represent the problem you want to solve? irlba can be applied to the latter to obtain just the first few principal components, anyway, so you get the best of both worlds. –  whuber Aug 27 '12 at 20:54
I suppose the latter. =). So I need to calculate the dot product for each pair of columns in my sparse matrix, subtract the colMeans of the sparse matrix from the dot product matrix, then run irlba on the result? –  Zach Aug 27 '12 at 21:11
Almost: notice you're subtracting products of column means, not the column means themselves. Your formulation of the algorithm otherwise is excellent, because although abstractly you're computing $X X'$, you don't really want R to create $X'$ in order to do the matrix multiplication. Instead, if RAM is really limited, you can perform the column dot products in batches by reading in subsets of the columns at a time. It would be wise to experiment with much smaller matrices at first :-). –  whuber Aug 27 '12 at 21:20
I added code to illustrate. –  whuber Jul 17 at 19:56


text:
6-conclusion.tex 4.98 KB
 Peter Schwabe committed Jun 20, 2019 1 \section{Conclusion}  Benoit Viguier committed Aug 12, 2019 2 \label{sec:Conclusion}  Peter Schwabe committed Jun 20, 2019 3   Benoit Viguier committed Jul 10, 2019 4 5 Any formal system relies on a trusted base. In this section we describe our chain of trust.  Peter Schwabe committed Jun 20, 2019 6   Benoit Viguier committed Sep 02, 2019 7 8 9 10 \subheading{Trusted Code Base of the proof.} Our proof relies on a trusted base, i.e. a foundation of definitions that must be correct. One should not be able to prove a false statement in that system, \eg, by proving an inconsistency.  Benoit Viguier committed Jul 10, 2019 11 12 13  In our case we rely on: \begin{itemize}  Benoit Viguier committed Sep 27, 2019 14  \item \textbf{Calculus of Inductive Constructions}. The intuitionistic logic  Benoit Viguier committed Jul 10, 2019 15  used by Coq must be consistent in order to trust the proofs. As an axiom,  Peter Schwabe committed Sep 29, 2019 16  we assume that the functional extensionality is also consistent with that logic.  Benoit Viguier committed Aug 16, 2019 17  $$\forall x, f(x) = g(x) \implies f = g$$  Benoit Viguier committed Jul 10, 2019 18 19 20 21 22 23 \begin{lstlisting}[language=Coq] Lemma f_ext: forall (A B:Type), forall (f g: A -> B), (forall x, f(x) = g(x)) -> f = g. \end{lstlisting}  Benoit Viguier committed Aug 01, 2019 24  \item \textbf{Verifiable Software Toolchain}. This framework developed at  Benoit Viguier committed Aug 21, 2019 25  Princeton allows a user to prove that a Clight code matches pure Coq  Benoit Viguier committed Sep 02, 2019 26  specification.  Benoit Viguier committed Jul 10, 2019 27   Freek Wiedijk committed Oct 01, 2019 28  \item \textbf{CompCert}.  Benoit Viguier committed Jan 16, 2020 29 30 31 32  When compiling with CompCert we only need to trust CompCert's {assembly} semantics, because it has been formally proven correct. However, when compiling with other C compilers like Clang or GCC, we need to trust that the CompCert's Clight semantics matches the C17 standard.  Benoit Viguier committed Jul 10, 2019 33   Freek Wiedijk committed Oct 01, 2019 34 35  \item \textbf{\texttt{clightgen}}. The tool making the translation from {C} to {Clight}. It is the first step of the compilation.  Benoit Viguier committed Jul 10, 2019 36 37 38 39 40 41 42  VST does not support the direct verification of \texttt{o[i] = a[i] + b[i]}. This required us to rewrite the lines into: \begin{lstlisting}[language=C] aux1 = a[i]; aux2 = b[i]; o[i] = aux1 + aux2; \end{lstlisting}  Peter Schwabe committed Sep 29, 2019 43  The trust of the proof relies on the trust of a correct translation from the  Benoit Viguier committed Sep 02, 2019 44 45  initial version of \emph{TweetNaCl} to \emph{TweetNaclVerifiableC}. \texttt{clightgen} comes with \texttt{-normalize} flag which  Benoit Viguier committed Aug 17, 2019 46  factors out function calls and assignments from inside subexpressions.  Peter Schwabe committed Sep 29, 2019 47  The changes required for C code to make it verifiable are now minimal.  Benoit Viguier committed Jul 10, 2019 48   Benoit Viguier committed Jan 16, 2020 49  \item Finally, we must trust the \textbf{Coq kernel} and its  Benoit Viguier committed Jul 10, 2019 50 51 52 53  associated libraries; the \textbf{Ocaml compiler} on which we compiled Coq; the \textbf{Ocaml Runtime} and the \textbf{CPU}. Those are common to all proofs done with this architecture \cite{2015-Appel,coq-faq}. \end{itemize}  Peter Schwabe committed Jun 20, 2019 54   Benoit Viguier committed Jan 16, 2020 55 56 \todo{NEW}  Benoit Viguier committed Sep 02, 2019 57 \subheading{Corrections in TweetNaCl.}  Benoit Viguier committed Aug 17, 2019 58 As a result of this verification, we removed superfluous code.  Benoit Viguier committed Sep 02, 2019 59 60 61 Indeed indexes 17 to 79 of the \TNaCle{i64 x[80]} intermediate variable of \TNaCle{crypto_scalarmult} were adding unnecessary complexity to the code, we removed them.  Benoit Viguier committed Aug 17, 2019 62 63  Peter Wu and Jason A. Donenfeld brought to our attention that the original  Benoit Viguier committed Oct 01, 2019 64 \TNaCle{car25519} function carried a risk of undefined behavior if \texttt{c}  Benoit Viguier committed Aug 17, 2019 65 66 67 68 69 is a negative number. \begin{lstlisting}[language=Ctweetnacl] c=o[i]>>16; o[i]-=c<<16; // c < 0 = UB ! \end{lstlisting}  Peter Schwabe committed Sep 29, 2019 70 71 We replaced this statement with a logical \texttt{and}, proved correctness, and thus solved this problem.  Benoit Viguier committed Aug 17, 2019 72 73 74 \begin{lstlisting}[language=Ctweetnacl] o[i]&=0xffff; \end{lstlisting}  Benoit Viguier committed Aug 12, 2019 75   Benoit Viguier committed Jan 17, 2020 76 \todo{NEW}  Benoit Viguier committed Jan 16, 2020 77   Benoit Viguier committed Jan 17, 2020 78 79 80 81 82 83 Aside from the modications above mentionned, all subsequent alteration ---such as the type change of loop indexes (\TNaCle{int} instead of \TNaCle{i64})--- were required for VST to parse properly the code. We believe those adjustments do not impact the trust of our proof. We contacted the authors of TweetNaCl and expect that the changes above  Benoit Viguier committed Jan 16, 2020 84 85 86 87 88 89 90 91 92 mentionned will soon be integrated in a new version of the library. \subheading{Extending our work.} The high-level definition (\sref{sec:maths}) can easily be ported to any other Montgomery curves and with it the proof of the ladder's correctness assuming the same forumlas are used. In addition to the curve equation, the field \F{p} would need to be redefined as $p=2^{255}-19$ is hard-coded in order to speed up some proofs.  Benoit Viguier committed Jan 17, 2020 93 94 95 96 97 98 99 100 With respect to the C code verification (\sref{sec:C-Coq}), the extension of the verification effort to Ed25519 would makes directly use of the low level arithmetic. The ladder steps formula being different this would require a high level verification similar to \tref{thm:montgomery-ladder-correct}. The verification \eg X448~\cite{cryptoeprint:2015:625,rfc7748} in C would require the adaptation of most of the low level arithmetic (mainly the multiplication, carry propagations and reductions).  Benoit Viguier committed Jan 16, 2020 101 102 103 Once the correctness and bounds of the basic operations are established, reproving the full ladder would make use of our generic definition and lower the workload.  Benoit Viguier committed Aug 12, 2019 104   Benoit Viguier committed Sep 02, 2019 105 \subheading{A complete proof.}  Benoit Viguier committed Sep 21, 2019 106 107 108 109 We provide a mechanized formal proof of the correctness of the X25519 implementation in TweetNaCl. We first formalized X25519 from RFC~7748~\cite{rfc7748} in Coq. Then we proved that TweetNaCl's implementation of X25519 matches our formalization.  Benoit Viguier committed Sep 02, 2019 110 In a second step we extended the Coq library for elliptic curves \cite{BartziaS14}  Benoit Viguier committed Sep 02, 2019 111 by Bartzia and Strub to support Montgomery curves. Using this extension we  Benoit Viguier committed Sep 27, 2019 112 proved that the X25519 from the RFC and therefore its implementation in TweetNaCl matches  Benoit Viguier committed Sep 21, 2019 113 the mathematical definitions as given in~\cite[Sec.~2]{Ber06}.


text:
# Justifying an early equation from *Introduction to Statistical Learning* [duplicate]

I'm self-studying Introduction to Statistical Learning. Page 19 of the book states the following:

Consider a given estimate $\hat{f}$ and a set of predictors $X$, which yields the prediction $\hat{Y} = \hat{f}(X)$. Assume for a moment that both $\hat{f}$ and $X$ are fixed. Then, it is easy to show that

$$E(Y-\hat{Y})^2 = E[f(X) + \epsilon - \hat{f}(X)]^2 = [f(X) = \hat{f}(X)]^2 + Var(\epsilon)$$

Question: How exactly is the step from $E[f(X) + \epsilon - \hat{f}(X)]^2$ to $[f(X) = \hat{f}(X)]^2 + Var(\epsilon)$ justified?


text:
# Exportation (logic)

Exportation[1][2][3][4] is a valid rule of replacement in propositional logic. The rule allows conditional statements having conjunctive antecedents to be replaced by statements having conditional consequents and vice-versa in logical proofs. It is the rule that:

$((P \and Q) \to R) \Leftrightarrow (P \to (Q \to R))$

Where "$\Leftrightarrow$" is a metalogical symbol representing "can be replaced in a proof with."

## Formal notation

The exportation rule may be written in sequent notation:

$((P \and Q) \to R) \vdash (P \to (Q \to R))$

where $\vdash$ is a metalogical symbol meaning that $(P \to (Q \to R))$ is a syntactic consequence of $((P \and Q) \to R)$ in some logical system;

or in rule form:

$\frac{(P \and Q) \to R}{P \to (Q \to R)}.$

where the rule is that wherever an instance of "$(P \and Q) \to R$" appears on a line of a proof, it can be replaced with "$P \to (Q \to R)$";

or as the statement of a truth-functional tautology or theorem of propositional logic:

$((P \and Q) \to R)) \to (P \to (Q \to R)))$

where $P$, $Q$, and $R$ are propositions expressed in some logical system.

## Natural language

### Truth values

At any time, if P→Q is true, it can be replaced by P→(P∧Q).
One possible case for P→Q is for P to be true and Q to be true; thus P∧Q is also true, and P→(P∧Q) is true.
Another possible case sets P as false and Q as true. Thus, P∧Q is false and P→(P∧Q) is false; false→false is true.
The last case occurs when both P and Q are false. Thus, P∧Q is false and P→(P∧Q) is true.

### Example

It rains and the sun shines implies that there is a rainbow.
Thus, if it rains, then the sun shines implies that there is a rainbow.

## Relation to functions

Exportation is associated with Currying via the Curry–Howard correspondence.

## References

1. ^ Hurley, Patrick (1991). A Concise Introduction to Logic 4th edition. Wadsworth Publishing. pp. 364–5.
2. ^ Copi, Irving M.; Cohen, Carl (2005). Introduction to Logic. Prentice Hall. p. 371.
3. ^ Moore and Parker
4. ^ http://www.philosophypages.com/lg/e11b.htm


text:
Probability the longer segment is at least twice as long as the shorter

A point is selected at random from the interval (0; 1); it then divides this interval into two segments. What is the probability that the longer segment is at least twice as long as the shorter segment?

Do we treat it as a uniform random variable and use the normalization rule to get f(x) and F(x)? I'm not really sure.

-
Could you give a title which indicates what the question is about? –  Asaf Karagila Sep 19 '12 at 13:07

The points between 0 and 1/3, together with the points between 2/3 and 1, constitute two-thirds of the interval $(0,1)$; that means there's a 2 out of 3 chance. –  Gerry Myerson Sep 20 '12 at 1:06


text:
# Tag Info

The paper The Relationship between Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms contains some results of interest, although they are somewhat technical. Specifically, it needs: Smoothness Assumption: For $n\in\mathbb{N}$, define $\nu(n)$ to be the minimum, over $d\in [n-2\sqrt{n}+1, n+2\sqrt{n}+1]$ of the largest prime factor of $d$...